Submission #355626

#	Time	Username	Problem	Language	Result	Execution time	Memory
355626		AmineTrabelsi	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	48 ms	17004 KiB

apple

#include "bits/stdc++.h"
using namespace std;
// Hi 
const int M = 1e6;
int a[M+5],tree[M*4],mark[M*4];
void push(int v){
    if(mark[v]){
        tree[v*2] = tree[v*2+1] = tree[v];
        mark[v*2] = mark[v*2+1] = 1;
        mark[v] = 0;
    }
}
void range_update(int v,int tl,int tr,int ql,int qr){
    if(ql > qr)return;
    if(ql == tl && qr == tr){
        tree[v] = 1;
        mark[v] = 1;
    }else{
        push(v);
        int mid = (tl+tr)/2;
        range_update(v*2,tl,mid,ql,min(qr,mid));
        range_update(v*2+1,mid+1,tr,max(mid+1,ql),qr);
    }
}
int range_query(int v,int tl,int tr,int ql,int qr){
    if(tl > qr || tr < ql)return 0;
    if(tl >= ql && tr <= qr && mark[v]){
        return tr-tl+1;
    }
    if(tl == tr)return mark[v];
    push(v);
    int mid = (tl+tr)/2;
    return range_query(v*2,tl,mid,ql,min(qr,mid))+
            range_query(v*2+1,mid+1,tr,max(ql,mid+1),qr);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int q;
    cin>>q;
    int c =  0;
    while(q--){
        int t;
        cin>>t;
        if(t == 1){
            int x,y;
            cin>>x>>y;
            x += c-1;
            y += c-1;
            int ans = range_query(1,0,M-1,x,y);
            c = ans;
            cout << ans << '\n';
        }else{
            int x,y;
            cin>>x>>y;
            x += c-1;
            y += c-1;
            range_update(1,0,M-1,x,y);
        }
    }
    return 0;
}

• Subtask 1: 0 / 100