oj.uz

Submission #680811

# Submission time Handle Problem Language Result Execution time Memory
680811 2023-01-11T20:21:39 Z stevancv trapezoid (balkan11_trapezoid) C++17
0 / 100
 113 ms 43240 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 {
    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));
}
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 10 ms 14648 KB Execution killed with signal 11
2 Runtime error 10 ms 14660 KB Execution killed with signal 11
3 Runtime error 11 ms 14804 KB Execution killed with signal 6
4 Runtime error 12 ms 15060 KB Execution killed with signal 6
5 Runtime error 12 ms 15236 KB Execution killed with signal 11
6 Runtime error 14 ms 15572 KB Execution killed with signal 11
7 Runtime error 14 ms 15828 KB Execution killed with signal 11
8 Runtime error 15 ms 16212 KB Execution killed with signal 6
9 Runtime error 19 ms 17596 KB Execution killed with signal 11
10 Runtime error 30 ms 20488 KB Execution killed with signal 11
11 Runtime error 36 ms 21892 KB Execution killed with signal 11
12 Runtime error 61 ms 28956 KB Execution killed with signal 11
13 Runtime error 76 ms 31808 KB Execution killed with signal 11
14 Runtime error 84 ms 34744 KB Execution killed with signal 11
15 Runtime error 92 ms 36132 KB Execution killed with signal 11
16 Runtime error 96 ms 37712 KB Execution killed with signal 11
17 Runtime error 98 ms 39028 KB Execution killed with signal 11
18 Runtime error 107 ms 40420 KB Execution killed with signal 11
19 Runtime error 110 ms 41792 KB Execution killed with signal 11
20 Runtime error 113 ms 43240 KB Execution killed with signal 11