oj.uz

Submission #1094162

# Submission time Handle Problem Language Result Execution time Memory
1094162 2024-09-28T18:53:59 Z VMaksimoski008 trapezoid (balkan11_trapezoid) C++17
100 / 100
 266 ms 32760 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ar array

const int mod = 30013;

struct SegTree {
    int n;
    vector<ar<int, 2> > tree;

    SegTree(int _n) : n(_n), tree(4*_n, {0, 0}) {}

    ar<int, 2> merge(ar<int, 2> a, ar<int, 2> b) {
        if(a[0] > b[0]) return a;
        if(a[0] < b[0]) return b;
        return { a[0], (a[1] + b[1]) % mod };
    }

    void update(int u, int tl, int tr, int p, int v, int w) {
        if(tl == tr) {
            tree[u] = merge(tree[u], { v, w });
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, p, v, w);
            else update(2*u+1, tm+1, tr, p, v, w);
            tree[u] = merge(tree[2*u], tree[2*u+1]);
        }
    }

    ar<int, 2> query(int u, int tl, int tr, int l, int r) {
        if(l > tr || tl > r) return { 0, 0 };
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return merge(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void update(int p, int v, int w) { update(1, 0, n-1, p, v, w); }
    ar<int, 2> query(int l, int r) { return query(1, 0, n-1, l, r); }
};

int main() {
    int n; cin >> n;
    vector<ar<int, 4> > v(n);
    set<int> s;
    for(int i=0; i<n; i++) {
        for(int j=0; j<4; j++) cin >> v[i][j];
        for(int j=0; j<4; j++) s.insert(v[i][j]);
    }

    vector<int> comp(s.begin(), s.end());
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++)
        for(int j=0; j<4; j++) v[i][j] = lower_bound(comp.begin(), comp.end(), v[i][j]) - comp.begin();

    vector<ar<int, 2> > dp(n);
    SegTree tree(comp.size());
    priority_queue<ar<int, 2> > pq;
    for(int i=0; i<n; i++) {
        dp[i] = { 1, 1 };
        while(!pq.empty() && -pq.top()[0] < v[i][0]) {
            tree.update(v[pq.top()[1]][3], dp[pq.top()[1]][0], dp[pq.top()[1]][1]);
            pq.pop();
        }
        auto res = tree.query(0, v[i][2]-1);
        if(res[0]) dp[i] = { res[0] + 1, res[1] };
        pq.push({ -v[i][1], i }); 
    }

    while(!pq.empty()) {
        tree.update(v[pq.top()[1]][3], dp[pq.top()[1]][0], dp[pq.top()[1]][1]);
        pq.pop();
    }
    auto [mx, ways] = tree.query(0, comp.size() - 1);
    cout << mx << " " << ways << '\n';
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 356 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 612 KB Output is correct
5 Correct 5 ms 1124 KB Output is correct
6 Correct 8 ms 1372 KB Output is correct
7 Correct 6 ms 1116 KB Output is correct
8 Correct 10 ms 1884 KB Output is correct
9 Correct 20 ms 3744 KB Output is correct
10 Correct 34 ms 4688 KB Output is correct
11 Correct 59 ms 9044 KB Output is correct
12 Correct 121 ms 18520 KB Output is correct
13 Correct 149 ms 21072 KB Output is correct
14 Correct 177 ms 25940 KB Output is correct
15 Correct 186 ms 23316 KB Output is correct
16 Correct 221 ms 24916 KB Output is correct
17 Correct 223 ms 29776 KB Output is correct
18 Correct 167 ms 19796 KB Output is correct
19 Correct 237 ms 32084 KB Output is correct
20 Correct 266 ms 32760 KB Output is correct