Submission #1079642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079642		codexistent	trapezoid (balkan11_trapezoid)	C++14	40 / 100	185 ms	13112 KiB

trapezoid

#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 (stderr)

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 / 100