Submission #1079606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079606		codexistent	trapezoid (balkan11_trapezoid)	C++14	0 / 100	47 ms	65536 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 * 4], stn[MAXN * 4];
pair<int, int> sp[MAXN], ep[MAXN];
pair<int, short> dp[MAXN];
queue<pair<int, int>> lz[MAXN * 4];

void push_n(int i, int l, int r){
    while(!lz[i].empty()){
        auto lzi = lz[i].front(); lz[i].pop();
        // if(lzi.f != 0) cout << " MGMGMG " << i << " => " << (stn[i] * (lzi.f != 0) + lzi.s) << endl;
        stn[i] = (stn[i] * (lzi.f != 0) + lzi.s) % MOD;

        if(l != r) lz[i * 2].push(lzi), lz[i * 2 + 1].push(lzi);
    }
}

int query_n(int i, int l, int r, int qry){
    push_n(i, l, r);
    if(qry < l || r < qry) return 0;
    
    if(l == r) return stn[i];
    return (query_n(i * 2, l, (l + r) / 2, qry) + query_n(i * 2 + 1, (l + r) / 2 + 1, r, qry)) % MOD;
}

void update_n(int i, int l, int r, pair<int, int> rng, pair<int, int> upd){
    // if(rng.f == 5 && rng.s == 14) cout << "HERE -> " << i << " of rng " << l << " " << r << endl;
    push_n(i, l, r);
    if(rng.s < l || r < rng.f) return;

    if(rng.f <= l && r <= rng.s) {
        // cout << " \--> HERERO " << endl;
        lz[i].push(upd);
        push_n(i, l, r);
        return;
    }
    update_n(i * 2, l, (l + r) / 2, rng, upd);
    update_n(i * 2 + 1, (l + r) / 2 + 1, r, rng, upd);
}

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] = stn[i] = 0;

    update_n(1, 0, 2 * n, {0, 2 * n}, {0, 1});
    /* 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;
            dp[i].s = query_n(1, 0, 2 * n, sp[i].s - 1) % MOD;
            // 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
                update_n(1, 0, 2 * n, {ep[i].s, lo}, {0, dp[i].s});
                // 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
            update_n(1, 0, 2 * n, {si, lo}, {1, dp[i].s});
            /*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; */
        }
    }

    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:90:49: warning: iteration 400020 invokes undefined behavior [-Waggressive-loop-optimizations]
   90 |     FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
      |                                          ~~~~~~~^~~
trapezoid.cpp:5:39: note: within this loop
    5 | #define FOR(i, a, b) for(int i = a; i <= b; i++)
......
   90 |     FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
      |         ~~~~~~~~~~~~~~~~~~~~~~         
trapezoid.cpp:90:5: note: in expansion of macro 'FOR'
   90 |     FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
      |     ^~~
trapezoid.cpp:90:49: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [1600080, 3200159] is out of the bounds [0, 1600080] of object 'stn' with type 'int [400020]' [-Warray-bounds]
   90 |     FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
      |                                          ~~~~~~~^~~
trapezoid.cpp:9:23: note: 'stn' declared here
    9 | int n, stc[MAXN * 4], stn[MAXN * 4];
      |                       ^~~
trapezoid.cpp:90:40: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [1600080, 3200159] is out of the bounds [0, 1600080] of object 'stc' with type 'int [400020]' [-Warray-bounds]
   90 |     FOR(i, 0, MAXN * 2 * 4 - 1) stc[i] = stn[i] = 0;
      |                                 ~~~~~~~^~~~~~~~~~~~
trapezoid.cpp:9:8: note: 'stc' declared here
    9 | int n, stc[MAXN * 4], stn[MAXN * 4];
      |        ^~~

• Subtask 1: 0 / 100