oj.uz

Submission #567391

# Submission time Handle Problem Language Result Execution time Memory
567391 2022-05-23T11:48:36 Z hgmhc trapezoid (balkan11_trapezoid) C++17
100 / 100
 159 ms 5272 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 = 3e5+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]%30013;
            else if (t[2*k] > t[2*k+1]) c[k] = c[2*k]%30013;
            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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 7 ms 676 KB Output is correct
9 Correct 14 ms 1012 KB Output is correct
10 Correct 23 ms 1492 KB Output is correct
11 Correct 32 ms 1716 KB Output is correct
12 Correct 70 ms 2988 KB Output is correct
13 Correct 82 ms 3340 KB Output is correct
14 Correct 102 ms 3816 KB Output is correct
15 Correct 116 ms 4164 KB Output is correct
16 Correct 135 ms 4568 KB Output is correct
17 Correct 133 ms 4672 KB Output is correct
18 Correct 113 ms 4820 KB Output is correct
19 Correct 144 ms 4836 KB Output is correct
20 Correct 159 ms 5272 KB Output is correct