oj.uz

Submission #680807

# Submission time Handle Problem Language Result Execution time Memory
680807 2023-01-11T20:14:40 Z stevancv trapezoid (balkan11_trapezoid) C++14
0 / 100
 114 ms 46020 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)
#define sadd(a, b) a = Add(a, b)
#define smul(a, b) a = Mul(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 {
    Node() {
        x = y = 0;
    }
    Node(int a, int b) {
        x = a; y = b;
    }
    int x, y;
};
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));
}
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());
    v.erase(unique(v.begin(), v.end()), 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 << en;
    cout << sol << en;
    return 0;
}

Compilation message

trapezoid.cpp: In function 'Node Merge(Node, Node)':
trapezoid.cpp:32:1: warning: no return statement in function returning non-void [-Wreturn-type]
   32 | }
      | ^
trapezoid.cpp: In function 'void Set(int, int, int, int, int, int)':
trapezoid.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = l + r >> 1;
      |               ~~^~~
trapezoid.cpp: In function 'Node Get(int, int, int, int, int)':
trapezoid.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 14660 KB Execution killed with signal 11
2 Runtime error 10 ms 14676 KB Execution killed with signal 11
3 Runtime error 10 ms 14932 KB Execution killed with signal 6
4 Runtime error 10 ms 15060 KB Execution killed with signal 6
5 Runtime error 11 ms 15312 KB Execution killed with signal 11
6 Runtime error 12 ms 15700 KB Execution killed with signal 11
7 Runtime error 15 ms 15948 KB Execution killed with signal 11
8 Runtime error 14 ms 16276 KB Execution killed with signal 6
9 Runtime error 19 ms 17732 KB Execution killed with signal 11
10 Runtime error 29 ms 20944 KB Execution killed with signal 11
11 Runtime error 33 ms 22536 KB Execution killed with signal 11
12 Runtime error 61 ms 30380 KB Execution killed with signal 11
13 Runtime error 73 ms 33480 KB Execution killed with signal 11
14 Runtime error 84 ms 36700 KB Execution killed with signal 11
15 Runtime error 87 ms 38204 KB Execution killed with signal 11
16 Runtime error 92 ms 39800 KB Execution killed with signal 11
17 Runtime error 101 ms 41340 KB Execution killed with signal 11
18 Runtime error 102 ms 42808 KB Execution killed with signal 11
19 Runtime error 105 ms 44376 KB Execution killed with signal 11
20 Runtime error 114 ms 46020 KB Execution killed with signal 11