oj.uz

Submission #680809

# Submission time Handle Problem Language Result Execution time Memory
680809 2023-01-11T20:17:37 Z stevancv trapezoid (balkan11_trapezoid) C++14
0 / 100
 114 ms 43392 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 << sp << 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 11 ms 14724 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 15056 KB Execution killed with signal 6
5 Runtime error 11 ms 15312 KB Execution killed with signal 11
6 Runtime error 15 ms 15684 KB Execution killed with signal 11
7 Runtime error 14 ms 15984 KB Execution killed with signal 11
8 Runtime error 14 ms 16340 KB Execution killed with signal 6
9 Runtime error 21 ms 17628 KB Execution killed with signal 11
10 Runtime error 30 ms 20544 KB Execution killed with signal 11
11 Runtime error 34 ms 21968 KB Execution killed with signal 11
12 Runtime error 76 ms 29096 KB Execution killed with signal 11
13 Runtime error 74 ms 31964 KB Execution killed with signal 11
14 Runtime error 80 ms 34820 KB Execution killed with signal 11
15 Runtime error 90 ms 36368 KB Execution killed with signal 11
16 Runtime error 93 ms 37748 KB Execution killed with signal 11
17 Runtime error 95 ms 39120 KB Execution killed with signal 11
18 Runtime error 98 ms 40564 KB Execution killed with signal 11
19 Runtime error 109 ms 42104 KB Execution killed with signal 11
20 Runtime error 114 ms 43392 KB Execution killed with signal 11