oj.uz

답안 #680817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680817 2023-01-11T20:28:12 Z stevancv 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
 185 ms 21372 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int mod = 30013;
int Add(int a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    return a;
}
struct Node {
    int x, y;
    Node() {
        x = y = 0;
    }
    Node(int a, int b) {
        x = a; y = b;
    }
};
Node Merge(Node a, Node b) {
    Node c;
    if (a.x > b.x) c = a;
    else if (a.x < b.x) c = b;
    else c = Node(a.x, Add(a.y, b.y));
    return c;
}
Node st[8 * N];
void Set(int node, int l, int r, int p, int x, int y) {
    if (l == r) {
        st[node] = Node(x, y);
        return;
    }
    int mid = l + r >> 1;
    if (p <= mid) Set(2 * node, l, mid, p, x, y);
    else Set(2 * node + 1, mid + 1, r, p, x, y);
    st[node] = Merge(st[2 * node], st[2 * node + 1]);
}
Node Get(int node, int l, int r, int ql, int qr) {
    if (r < ql || qr < l) return Node();
    if (ql <= l && r <= qr) return st[node];
    int mid = l + r >> 1;
    return Merge(Get(2 * node, l, mid, ql, qr), Get(2 * node + 1, mid + 1, r, ql, qr));
}
Node ans[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    vector<int> a(n), b(n), c(n), d(n);
    vector<array<int, 3>> all;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        all.push_back({a[i], i, 0});
        all.push_back({b[i], i, 1});
        v.push_back(c[i]); v.push_back(d[i]);
    }
    sort(v.begin(), v.end());
    sort(all.begin(), all.end());
    map<int, int> mp;
    int x = 0;
    for (int i : v) mp[i] = x++;
    for (auto u : all) {
        if (u[2] == 0) {
            ans[u[1]] = Get(1, 0, x - 1, 0, mp[c[u[1]]]);
            ans[u[1]].x += 1;
            if (ans[u[1]].x == 1) ans[u[1]].y += 1;
        }
        else Set(1, 0, x - 1, mp[d[u[1]]], ans[u[1]].x, ans[u[1]].y);
    }
    int mx = 0;
    for (int i = 0; i < n; i++) smax(mx, ans[i].x);
    int sol = 0;
    for (int i = 0; i < n; i++) if (ans[i].x == mx) sol = Add(sol, ans[i].y);
    cout << mx << sp << sol << en;
    return 0;
}

Compilation message

trapezoid.cpp: In function 'void Set(int, int, int, int, int, int)':
trapezoid.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~
trapezoid.cpp: In function 'Node Get(int, int, int, int, int)':
trapezoid.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7492 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 7 ms 7764 KB Output is correct
7 Correct 8 ms 7892 KB Output is correct
8 Correct 10 ms 8020 KB Output is correct
9 Correct 18 ms 8720 KB Output is correct
10 Correct 36 ms 10112 KB Output is correct
11 Correct 44 ms 10876 KB Output is correct
12 Correct 86 ms 14340 KB Output is correct
13 Correct 105 ms 15744 KB Output is correct
14 Correct 129 ms 17272 KB Output is correct
15 Correct 143 ms 17916 KB Output is correct
16 Correct 156 ms 18604 KB Output is correct
17 Correct 165 ms 19448 KB Output is correct
18 Correct 131 ms 20036 KB Output is correct
19 Correct 170 ms 20692 KB Output is correct
20 Correct 185 ms 21372 KB Output is correct