oj.uz

Submission #567387

# Submission time Handle Problem Language Result Execution time Memory
567387 2022-05-23T11:44:48 Z hgmhc trapezoid (balkan11_trapezoid) C++17
60 / 100
 125 ms 6900 KB 
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
void o_o(){ cerr << endl; }
template <class H, class...T> void o_o(H h,T...t) { cerr << ' ' << h; o_o(t...); }
#define debug(...) cerr<<'['<<#__VA_ARGS__<<"]:",o_o(__VA_ARGS__)
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define size(x) int((x).size())
#define fi first
#define se second
#define Mup(x,y) x = max(x,y)

const int N = 1e5+3;
int n;
priority_queue<pair<ii,ii>,vector<pair<ii,ii>>,greater<>> pq;
struct segment_tree {
    int t[2*N], c[2*N];
    void update(int k, int v1, int v2) {
        k += N;
        for (t[k] = v1, c[k] = v2%30013; (k /= 2) >= 1;) {
            if (t[2*k] < t[2*k+1]) c[k] = c[2*k+1];
            else if (t[2*k] > t[2*k+1]) c[k] = c[2*k];
            else c[k] = (c[2*k]+c[2*k+1])%30013;
            t[k] = max(t[2*k],t[2*k+1]);
        }
    }
    ii query(int a, int b) {
        int r = 0, s = 0;
        for (int x = a+N, y = b+N; x <= y; ++x /= 2, --y /= 2) {
            if (x&1) Mup(r,t[x]);
            if (~y&1) Mup(r,t[y]);
        }
        for (int x = a+N, y = b+N; x <= y; ++x /= 2, --y /= 2) {
            if (x&1) { if (t[x] == r) s = (s+c[x])%30013; }
            if (~y&1) { if (t[y] == r) s = (s+c[y])%30013; }
        }
        return {r,s};
    }
} ds;
pair<ii,ii> t[N];

void pre() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    vector<int> xs, ys;
    rep(i,1,n) {
        cin >> t[i].fi.fi >> t[i].se.fi;
        xs.push_back(t[i].fi.fi), xs.push_back(t[i].se.fi);
        cin >> t[i].fi.se >> t[i].se.se;
        ys.push_back(t[i].fi.se), ys.push_back(t[i].se.se);
    }
    sort(all(xs)), xs.erase(unique(all(xs)),end(xs));
    sort(all(ys)), ys.erase(unique(all(ys)),end(ys));
    rep(i,1,n) {
        t[i].fi.fi = lower_bound(all(xs),t[i].fi.fi)-begin(xs);
        t[i].fi.se = lower_bound(all(ys),t[i].fi.se)-begin(ys);
        t[i].se.fi = lower_bound(all(xs),t[i].se.fi)-begin(xs);
        t[i].se.se = lower_bound(all(ys),t[i].se.se)-begin(ys);
    }
    sort(t+1,t+n+1);
}
int main() {
    pre();
    rep(i,1,n) {
        auto [p1,p2] = t[i];
        // debug(p1.fi,p1.se,p2.fi,p2.se);
        // if (not empty(pq)) debug(pq.top().fi.fi,p1.fi);
        while (not empty(pq) and pq.top().fi.fi < p1.fi) {
            ds.update(pq.top().fi.se, pq.top().se.fi,pq.top().se.se);
            // debug(pq.top().fi.se, pq.top().se.fi);
            pq.pop();
        }
        auto [v1,v2] = ds.query(0,p1.se);
        if (v1 == 0) v2 = 1;
        // debug(v1+1,v2);
        pq.emplace(p2,ii{v1+1,v2});
    }
    while (not empty(pq)) {
        ds.update(pq.top().fi.se,pq.top().se.fi,pq.top().se.se);
        pq.pop();
    }
    auto [a1,a2] = ds.query(0,2*n+2);
    cout << a1 << ' ' << a2;
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 7 ms 736 KB Output is correct
9 Correct 15 ms 880 KB Output is correct
10 Correct 23 ms 1512 KB Output is correct
11 Correct 33 ms 1648 KB Output is correct
12 Correct 69 ms 2860 KB Output is correct
13 Runtime error 75 ms 5940 KB Execution killed with signal 11
14 Runtime error 86 ms 6124 KB Execution killed with signal 11
15 Runtime error 98 ms 6416 KB Execution killed with signal 11
16 Runtime error 101 ms 5708 KB Execution killed with signal 11
17 Runtime error 96 ms 6572 KB Execution killed with signal 11
18 Runtime error 106 ms 6900 KB Execution killed with signal 11
19 Runtime error 101 ms 6084 KB Execution killed with signal 11
20 Runtime error 125 ms 6548 KB Execution killed with signal 11