oj.uz

Submission #1079642

# Submission time Handle Problem Language Result Execution time Memory
1079642 2024-08-28T19:39:30 Z codexistent trapezoid (balkan11_trapezoid) C++14
40 / 100
 185 ms 13112 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MOD 30013
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define f first
#define s second

int n, stc[MAXN * 2 * 4];
pair<int, int> sp[MAXN], ep[MAXN];
pair<int, short> dp[MAXN];

int query_c(int i, int l, int r, pair<int, int> rng){
    if(rng.second < l || r < rng.first) return 0;

    if(rng.first <= l && r <= rng.second) return stc[i];
    return max(query_c(i * 2, l, (l + r) / 2, rng), query_c(i * 2 + 1, (l + r) / 2 + 1, r, rng));
}

void update_c(int i, int l, int r, pair<int, int> upd){
    if(upd.f < l || r < upd.f) return;

    if(l == r) {
        stc[i] = upd.s;
        return;
    }
    update_c(i * 2, l, (l + r) / 2, upd);
    update_c(i * 2 + 1, (l + r) / 2 + 1, r, upd);
    stc[i] = max(stc[i * 2], stc[i * 2 + 1]);
}

void update_n(int i, int l, int r, pair<int, int> upd){
    if(upd.f < l || r < upd.f) return;

    if(l == r) {
        stc[i] = upd.s;
        return;
    }
    update_n(i * 2, l, (l + r) / 2, upd);
    update_n(i * 2 + 1, (l + r) / 2 + 1, r, upd);
    stc[i] = (stc[i * 2] + stc[i * 2 + 1]) % MOD;
}

int query_n(int i, int l, int r, pair<int, int> rng){
    if(rng.second < l || r < rng.first) return 0;

    if(rng.first <= l && r <= rng.second) return stc[i];
    return (query_n(i * 2, l, (l + r) / 2, rng) + query_n(i * 2 + 1, (l + r) / 2 + 1, r, rng)) % MOD;
}

int main(){
    cin >> n;
    vector<pair<int, pair<int, int>>> ple;
    FOR(i, 1, n){
        cin >> sp[i].f >> ep[i].f;
        cin >> sp[i].s >> ep[i].s;
        ple.push_back({sp[i].s, {0, i}});
        ple.push_back({ep[i].s, {1, i}});
    }

    // coordinate compression
    vector<pair<int, pair<int, int>>> pls;
    sort(begin(ple), end(ple));
    FOR(i, 1, 2 * n){
        if(ple[i - 1].s.f == 0){
            sp[ple[i - 1].s.s].s = i;
            pls.push_back({sp[ple[i - 1].s.s].f, {0, ple[i - 1].s.s}});
        }else{
            ep[ple[i - 1].s.s].s = i;
            pls.push_back({ep[ple[i - 1].s.s].f, {1, ple[i - 1].s.s}});
        }
    }
    sort(begin(pls), end(pls));

    FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = 0;

    for(auto pi : pls){
        int i = pi.s.s;
        if(pi.s.f == 0){ // start point
            dp[i].f = query_c(1, 0, 2 * n, {0, sp[i].s - 1}) + 1;
        }else {
            update_c(1, 0, 2 * n, {ep[i].s, dp[i].f});
        }
    }

    // FOR(i, 1, n) cout << dp[i].f << endl;

    priority_queue<pair<int, pair<int, int>>> pq;
    FOR(i, 1, n) pq.push({-dp[i].f, {-sp[i].f, i}});

    FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = 0;
    dp[0].s = 1, ep[0].s = 0;
    update_n(1, 0, 2*n, {0, 1});

    /*FOR(i, 0, 2*n){
        cout << " " << query_n(1, 0, 2*n, {i, i});
    }
    cout << endl;*/

    int prv = pq.top().f, ptr = 1;
    vector<pair<int, int>> v2p, vp;
    v2p.push_back({0, 0});
    while(pq.size()){
        // cout << "QUERY " << -pq.top().f << " ~ " << -pq.top().s.f << " => " << pq.top().s.s << endl;

        if(pq.top().f != prv){
            // cout << -pq.top().f << " " << endl;
            for(auto i : v2p) {
                update_n(1, 0, 2 * n, {ep[i.s].s, 0});
                // cout << "  " << i.s << " ";
            }
            ptr = 0;
            // cout << endl;
            v2p.clear();
            swap(v2p, vp);
            sort(begin(v2p), end(v2p));
        }

        prv = pq.top().f;
        int i = pq.top().s.s; pq.pop();

        while(ptr != v2p.size() && v2p[ptr].f < sp[i].f){
            update_n(1, 0, 2 * n, {ep[v2p[ptr].s].s, dp[v2p[ptr].s].s});
            ptr++;
        }

        dp[i].s = query_n(1, 0, 2 * n, {0, sp[i].f - 1}) % MOD;
        vp.push_back({ep[i].f, i});

        /*FOR(i, 0, 2*n){
            cout << " " << query_n(1, 0, 2*n, {i, i});
        }
        cout << endl;*/
    }

    int cr = 0;
    FOR(i, 1, n) cr = max(cr, dp[i].f);
    cout << cr;
    /*int nr = 0;
    FOR(i, 1, n) if(dp[i].f == cr) nr = (nr + dp[i].s) % MOD;

    cout << " " << nr << endl;*/
    cout << " 1" << endl;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:122:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         while(ptr != v2p.size() && v2p[ptr].f < sp[i].f){
      |               ~~~~^~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 5720 KB Partially correct
2 Partially correct 1 ms 5724 KB Partially correct
3 Partially correct 2 ms 5724 KB Partially correct
4 Partially correct 2 ms 5724 KB Partially correct
5 Partially correct 4 ms 5864 KB Partially correct
6 Partially correct 6 ms 5980 KB Partially correct
7 Partially correct 7 ms 5904 KB Partially correct
8 Partially correct 9 ms 6104 KB Partially correct
9 Partially correct 20 ms 6484 KB Partially correct
10 Partially correct 31 ms 7248 KB Partially correct
11 Partially correct 46 ms 7700 KB Partially correct
12 Partially correct 91 ms 9532 KB Partially correct
13 Partially correct 111 ms 10048 KB Partially correct
14 Partially correct 127 ms 12868 KB Partially correct
15 Partially correct 147 ms 12856 KB Partially correct
16 Partially correct 159 ms 12540 KB Partially correct
17 Partially correct 165 ms 12596 KB Partially correct
18 Partially correct 144 ms 13112 KB Partially correct
19 Partially correct 171 ms 13108 KB Partially correct
20 Partially correct 185 ms 13112 KB Partially correct