Submission #1198410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198410		khalwsh	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	378 ms	254416 KiB

apple

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

void PRE() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
// #ifndef ONLINE_JUDGE
//     freopen("in.txt", "r", stdin);
//     freopen("out.txt", "w", stdout);
//     freopen("error.txt", "w", stderr);
// #endif
}
int n , q;
const int sz = 1e9;
struct dynamicSeg {
    int sum = 0;
    bool lazy = false;
    dynamicSeg *L = nullptr, *R = nullptr;

    void prop(int nl, int nr) {
        if (!lazy) return;
        // mark this entire node as all-1
        sum = (nr - nl + 1);
        if (nl != nr) {
            if (!L) L = new dynamicSeg();
            if (!R) R = new dynamicSeg();
            L->lazy = R->lazy = true;
        }
        lazy = false;
    }

    void add(int nl, int nr, int i, int j) {
        prop(nl, nr);
        if (nl > j || nr < i) return;
        if (nl >= i && nr <= j) {
            // full cover: mark lazy, then do a prop
            lazy = true;
            prop(nl, nr);
            return;
        }
        int mid = nl + (nr - nl) / 2;
        if (!L) L = new dynamicSeg();
        if (!R) R = new dynamicSeg();
        L->add(nl, mid, i, j);
        R->add(mid+1, nr, i, j);
        sum = L->sum + R->sum;
    }

    int query(int nl, int nr, int l, int r) {
        prop(nl, nr);
        if (nl > r || nr < l) return 0;
        if (nl >= l && nr <= r) return sum;
        int mid = nl + (nr - nl) / 2;
        return (L ? L->query(nl, mid, l, r) : 0)
             + (R ? R->query(mid+1, nr, l, r) : 0);
    }
};

int main() {
    PRE();
    int n;cin>>n;
    dynamicSeg dseg;
    int c = 0;
    for (int i = 0;i < n;i++) {
        int d;cin>>d;
        int l , r;cin>>l>>r;
        l += c , r += c;
        if (d == 1) {
            c = dseg.query(0 , sz - 1 , l , r);
            cout<<c<<'\n';
        }else {
            dseg.add(0 , sz - 1 , l , r);
        }
    }
}

• Subtask 1: 0 / 100