Submission #1370314

#TimeUsernameProblemLanguageResultExecution timeMemory
1370314AlesL0Monkey and Apple-trees (IZhO12_apple)C++20
100 / 100
302 ms207396 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;

ll coun = 0;

struct sparse {
    ll sum, lazy;
    sparse *left, *right;
    sparse () : sum(0), lazy(0), left(0), right(0) {};

    void prop(ll len){
        if (left == nullptr)left = new sparse();
        if (right == nullptr)right = new sparse();
        if (!lazy)return;
        (left->sum) = len;
        (right->sum) = len;
        (left->lazy) = 1;
        (right->lazy) = 1;
        lazy = 0;
    }

    void update(ll x, ll y, ll l, ll r){
        if (l >= x && r <= y){
            sum = r-l;
            lazy = 1;
            return;
        }
        if (l >= y || r <= x)return;
        prop((r-l)>>1);
        left->update(x, y, l, (l+r)>>1);
        right->update(x, y, (l+r)>>1, r);
        sum = (left->sum)+(right->sum);
    }

    ll range_sum(ll x, ll y, ll l, ll r){
        if (l >= x && r <= y)return sum;
        if (l >= y || r <= x)return 0;
        prop((r-l)>>1);
        return (left->range_sum(x, y, l, (l+r)>>1)+right->range_sum(x, y, (l+r)>>1, r));
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll m; cin >> m;
    sparse *t = new sparse();
    ll max_range = 1;
    while (max_range <= 1e9+1)max_range *= 2;
    while (m--){
        ll d, x, y; cin >> d >> x >> y;
        x += coun;
        y += coun+1;
        if (d == 1){
            ll s = (t->range_sum(x, y, 0, max_range));
            coun = s;
            cout << s << "\n";
        }
        else t->update(x, y, 0, max_range);
    }
}
#Result Execution timeMemoryGrader output
Fetching results...