Submission #1079608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079608		codexistent	trapezoid (balkan11_trapezoid)	C++14	0 / 100	283 ms	13536 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]);
}

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(i, 0, 2*n){
        cout << " " << query_n(1, 0, 2*n, i);
    }
    cout << endl;
    FOR(i, 0, 2*n){
        cout << " " << query_c(1, 0, 2*n, {i, i});
    }
    cout << endl; */
    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;
            // cout << "DP " << i << " EQUALS " << dp[i].f << " of ct " << dp[i].s << endl;
        }else{
            int qi = query_c(1, 0, 2 * n, {0, ep[i].s - 1});
            if(qi > dp[i].f) goto update;
            int lo = ep[i].s, hi = 2 * n;
            if(qi < dp[i].f){
                while(lo < hi){
                    int mid = (lo + hi + 1) / 2;
                    // cout << "   FINDING NEMOi FOR THE BELOW " << 0 << " to " << mid << " GIVES " << query_c(1, 0, 2 * n, {0, mid}) << endl;
                    if(query_c(1, 0, 2 * n, {0, mid}) < dp[i].f){
                        lo = mid;
                    }else{
                        hi = mid - 1;
                    }
                }

                // replace num valid ways with dp[i].s for range (ep[i].s)...lo
                // cout << " ALERT 1: we update " <<  ep[i].s << " TO " << lo << " with complete refurbish to " << dp[i].s << endl;
                /* FOR(i, 0, 2*n){
                    cout << " " << query_n(1, 0, 2*n, i);
                }
                cout << endl;
                FOR(i, 0, 2*n){
                    cout << " " << query_c(1, 0, 2*n, {i, i});
                }
                cout << endl; */

                if(lo == 2 * n) goto update;
                lo ++;
            }

            int si = lo;

            if(query_c(1, 0, 2 * n, {0, lo}) != dp[i].f) goto update;

            hi = 2 * n;
            while(lo < hi){
                // cout << ((lo + hi) / 2) << " => " << query_c(i, 0, 2 * n, {0, (lo + hi) / 2}) << endl;
                int mid = (lo + hi + 1) / 2;
                if(query_c(1, 0, 2 * n, {0, mid}) == dp[i].f){
                    lo = mid;
                }else{
                    hi = mid - 1;
                }
            }

            // add num valid ways with dp[i].s for range si...lo
            /*cout << " ALERT 2: we update " << si << " TO " << lo << " with add to " << dp[i].s << endl;
            FOR(j, 0, 2*n){
                cout << " " << query_n(1, 0, 2*n, j);
            }
            cout << endl;

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

        update:;
        if(pi.s.f == 1) {
            // cout << " => " << dp[i].f << endl;
            update_c(1, 0, 2 * n, {ep[i].s, dp[i].f});
            /* cout << " ALERT 3" << endl;
            FOR(i, 0, 2*n){
                cout << " " << query_c(1, 0, 2*n, {i, i});
            }
            cout << endl; */
        }
    }

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

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

    int prv = 0;
    stack<int> s;
    while(pq.size()){
        int i = pq.top().s; pq.pop();
    }

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

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

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:101:17: warning: unused variable 'si' [-Wunused-variable]
  101 |             int si = lo;
      |                 ^~

• Subtask 1: 0 / 100