Submission #1198407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198407		khalwsh	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	22 ms	840 KiB

apple

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M;
    cin >> M;

    // map of disjoint intervals [start -> end], always non-overlapping and merged
    map<ll,ll> cov;
    ll C = 0;

    while(M--){
        int D;
        ll X, Y;
        cin >> D >> X >> Y;
        ll l = X + C;
        ll r = Y + C;

        if(D == 2){
            // insert [l, r], merging with any overlapping/adjacent
            auto it = cov.lower_bound(l);
            // maybe step back to catch an interval that starts before l but overlaps
            if(it != cov.begin()){
                auto pit = prev(it);
                if(pit->second + 1 < l) {
                    // no overlap
                } else {
                    it = pit;
                }
            }
            // now merge all intervals that overlap or touch [l,r]
            ll nl = l, nr = r;
            while(it != cov.end() && it->first <= nr + 1){
                nl = min(nl, it->first);
                nr = max(nr, it->second);
                it = cov.erase(it);
            }
            cov[nl] = nr;
        } else {
            // query: sum up covered trees in [l, r]
            ll ans = 0;
            auto it = cov.lower_bound(l);
            if(it != cov.begin()){
                auto pit = prev(it);
                if(pit->second < l){
                    // does not overlap
                } else {
                    it = pit;
                }
            }
            // walk until intervals start beyond r
            for(; it != cov.end() && it->first <= r; ++it){
                ll il = max(it->first, l);
                ll ir = min(it->second, r);
                if(il <= ir)
                    ans += (ir - il + 1);
            }
            cout << ans << "\n";
            C = ans;
        }
    }

    return 0;
}

• Subtask 1: 100 / 100