oj.uz

Submission #1094160

# Submission time Handle Problem Language Result Execution time Memory
1094160 2024-09-28T18:49:13 Z VMaksimoski008 trapezoid (balkan11_trapezoid) C++17
100 / 100
 223 ms 30032 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 30013;
const int LOG = 20;
const int maxn = 1e5 + 5;

struct SegTree {
    int n;
    vector<pii> tree;

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

    pii merge(pii a, pii b) {
        if(a.first > b.first) return a;
        if(a.first < b.first) return b;
        return { a.first, (a.second + b.second) % 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]);
        }
    }

    pii 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); }
    pii query(int l, int r) { return query(1, 0, n-1, l, r); }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n; cin >> n;
    vector<array<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<pii> dp(n);
    SegTree tree(comp.size());
    priority_queue<pii> pq;
    for(int i=0; i<n; i++) {
        dp[i] = { 1, 1 };
        while(!pq.empty() && -pq.top().first < v[i][0]) {
            tree.update(v[pq.top().second][3], dp[pq.top().second].first, dp[pq.top().second].second);
            pq.pop();
        }
        auto res = tree.query(0, v[i][2]-1);
        if(res.first) dp[i] = { res.first + 1, res.second };
        pq.push({ -v[i][1], i }); 
    }

    while(!pq.empty()) {
        tree.update(v[pq.top().second][3], dp[pq.top().second].first, dp[pq.top().second].second);
        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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 3 ms 1116 KB Output is correct
6 Correct 4 ms 1372 KB Output is correct
7 Correct 6 ms 1116 KB Output is correct
8 Correct 8 ms 1628 KB Output is correct
9 Correct 17 ms 3540 KB Output is correct
10 Correct 24 ms 4188 KB Output is correct
11 Correct 49 ms 8532 KB Output is correct
12 Correct 101 ms 17136 KB Output is correct
13 Correct 118 ms 19540 KB Output is correct
14 Correct 147 ms 23984 KB Output is correct
15 Correct 156 ms 21332 KB Output is correct
16 Correct 179 ms 22868 KB Output is correct
17 Correct 203 ms 27468 KB Output is correct
18 Correct 116 ms 17172 KB Output is correct
19 Correct 182 ms 29436 KB Output is correct
20 Correct 223 ms 30032 KB Output is correct