Submission #1277247

#TimeUsernameProblemLanguageResultExecution timeMemory
1277247WarinchaiMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
425 ms327680 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

struct node{
    int info,lz;
    node *l,*r;
    node(int _i=0){
        info=_i;
        lz=0;
        l=r=NULL;
    }
};
typedef node* pnode;

struct segtree{
    pnode rt=NULL;
    segtree(){
        rt=new node();
    }
    void push(int st,int en,pnode &x){
        assert(x->lz==0||x->lz==1);
        if(x->lz==0)return;
        x->info=(en-st+1);
        if(st!=en){
            if(!(x->l))x->l=new node();
            if(!(x->r))x->r=new node();
            x->l->lz=1;
            x->r->lz=1;
        }
        x->lz=0;
    }
    void upd(int st,int en,pnode &x,int l,int r){
        if(!x)x=new node();
        push(st,en,x);
        if(st>r||en<l)return;
        if(st>=l&&en<=r)return x->lz=1,push(st,en,x);
        int m=(st+en)/2;
        upd(st,m,x->l,l,r);
        upd(m+1,en,x->r,l,r);
        x->info=x->l->info+x->r->info;
    }
    int fans(int st,int en,pnode &x,int l,int r){
        if(!x)return 0;
        push(st,en,x);
        if(st>r||en<l)return 0;
        if(st>=l&&en<=r){
            //cerr<<"l r:"<<st<<" "<<en<<":"<<x->info<<"\n";
            return x->info;
        }
        int m=(st+en)/2;
        return fans(st,m,x->l,l,r)+fans(m+1,en,x->r,l,r);
    }
}tr;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m;cin>>m;
    int c=0;
    for(int i=0;i<m;i++){
        int d,x,y;cin>>d>>x>>y;
        x+=c,y+=c;
        if(d==1){
            int temp=tr.fans(1,1e9+5,tr.rt,x,y);
            c=temp;
            cout<<temp<<"\n";
        }else{
            tr.upd(1,1e9+5,tr.rt,x,y);
            //cerr<<tr.fans(1,1e9,tr.rt,7,11)<<"\n";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...