제출 #1161673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1161673		AlgorithmWarrior	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	213 ms	52052 KiB

apple

#include <bits/stdc++.h>

using namespace std;

struct node{
    int cnt;
    int fiust,fiudr;
};

struct dyn_seg_tree{
    node v[12000000];
    int total;
    void propagate(int nod,int st,int mij,int dr){
        if(!v[nod].fiust)
            v[nod].fiust=++total;
        if(!v[nod].fiudr)
            v[nod].fiudr=++total;
        if(v[nod].cnt==dr-st+1){
            v[v[nod].fiust].cnt=mij-st+1;
            v[v[nod].fiudr].cnt=dr-mij;
        }
    }
    void add(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            v[nod].cnt=dr-st+1;
        else{
            int mij=(st+dr)/2;
            propagate(nod,st,mij,dr);
            if(a<=mij)
                add(v[nod].fiust,st,mij,a,b);
            if(b>mij)
                add(v[nod].fiudr,mij+1,dr,a,b);
            v[nod].cnt=v[v[nod].fiust].cnt+v[v[nod].fiudr].cnt;
        }
    }
    int sum(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            return v[nod].cnt;
        int mij=(st+dr)/2;
        propagate(nod,st,mij,dr);
        int s=0;
        if(a<=mij)
            s+=sum(v[nod].fiust,st,mij,a,b);
        if(b>mij)
            s+=sum(v[nod].fiudr,mij+1,dr,a,b);
        return s;
    }
}aint;

int constant;

void process_queries(){
    int q;
    cin>>q;
    while(q--){
        int type,l,r;
        cin>>type>>l>>r;
        l+=constant;
        r+=constant;
        if(type==1){
            constant=aint.sum(0,1,1e9,l,r);
            cout<<constant<<'\n';
        }
        else
            aint.add(0,1,1e9,l,r);
    }
}

int main()
{
    process_queries();
    return 0;
}

• Subtask 1: 100 / 100