Submission #1187471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187471		pacman	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	47 ms	66120 KiB

apple

#include <bits/stdc++.h>
#define int int64_t

using namespace std;

const int maxn = 1e6 + 10, lg = 21, sz = 1 << 20;

int Q, C;


struct segment_tree{
    int seg[2 << lg] , lazy[2 << lg];

    segment_tree(){
        for(int i = 0; i < (2 << lg); i++){
            seg[i] = lazy[i] = 0;
        }
    }

    void shift(int v ,int L, int R){
        if(L == R or lazy[v] == 0) return;

        int mid = (R + L) / 2;

        seg[v * 2] = (mid - L + 1);
        seg[v * 2 + 1] = (R - mid);
        lazy[v * 2]  = lazy[v * 2 + 1] = 1;
        
        lazy[v] = 0;
    }


    void calc(int v){
        seg[v] = seg[2 * v] + seg[2 * v + 1];
    }


    void update(int v ,int L, int R ,int l, int r){
        if(l > r or L > R or l > R or L > r){
            return;
        }
        if(l <= L and R <= r){
            seg[v] = (R - L + 1);
            lazy[v] = 1;
            return;
        }
        shift(v , L, R);
        int mid = (R + L) / 2;
        update(2 * v ,L ,mid ,l ,r);
        update(2 * v + 1, mid + 1, R ,l, r);
        calc(v);
    }


    int get(int v, int L, int R ,int l, int r){
        if(l > r or L > R or l > R or L > r){
            return 0;
        }
        if(l <= L and R <= r){
            return seg[v];
        }
        shift(v , L ,R);
        int mid = (R + L) / 2;
        return (get(2 * v ,L ,mid, l, r) + get(2 * v + 1, mid + 1 , R ,l, r));
    }   
}seg;


void in(){
    cin >> Q;
}


void out(){
    while(Q--){
        int type, l ,r;
        cin >> type >> l >> r;
        l--, r--;
        if(type == 1){
            int ans = seg.get(1 ,0 , sz - 1, l + C, r + C);
            C = ans;
            cout << ans << "\n";
        }
        else{
            seg.update(1 ,0, sz - 1, l + C , r + C);
        }
    }
}


int32_t main(){

    ios::sync_with_stdio(0) ,cout.tie(0) ,cin.tie(0);

    in();
    out();
    
    return 0;
}

• Subtask 1: 0 / 100