제출 #1366389

#제출 시각아이디문제언어결과실행 시간메모리
1366389jenterjongle45원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
141 ms94752 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
int idx=1;
struct node{
    int val,lz,l,r;
    node(){val=0,lz=0,l=-1,r=-1;}
}nodes[6000100];
struct segment{
    void flush(int il,int ir,int now){
        if(nodes[now].lz==0) return;
        nodes[now].val=ir-il+1;
        if(il!=ir){
            int mid=(il+ir)/2;
            if(nodes[now].l==-1) nodes[now].l=++idx;
            if(nodes[now].r==-1) nodes[now].r=++idx;
            nodes[nodes[now].l].lz=1;
            nodes[nodes[now].r].lz=1;
        }
        nodes[now].lz=0;
    }
    void upd(int il,int ir,int l,int r,int now){
        flush(il,ir,now);
        if(ir<l||il>r) return;
        if(l<=il&&ir<=r){
            nodes[now].lz=1;
            flush(il,ir,now);
            // cout<<il<<' '<<ir<<' '<<nodes[now].val<<'\n';
            return;
        }
        int mid=(il+ir)>>1;
        if(nodes[now].l==-1) nodes[now].l=++idx;
        if(nodes[now].r==-1) nodes[now].r=++idx;
        upd(il,mid,l,r,nodes[now].l);
        upd(mid+1,ir,l,r,nodes[now].r);
        nodes[now].val=nodes[nodes[now].l].val+nodes[nodes[now].r].val;
        // cout<<il<<' '<<ir<<' '<<nodes[nodes[now].l].val<<' '<<nodes[nodes[now].r].val<<'\n';
    }
    void upd(int l,int r){upd(1,1e9,l,r,1);}
    ll qry(int il,int ir,int l,int r,int now){
        flush(il,ir,now);
        if(ir<l||il>r) return 0;
        if(l<=il&&ir<=r){
            return nodes[now].val;
        }
        int mid=(il+ir)>>1;
        if(nodes[now].l==-1) nodes[now].l=++idx;
        if(nodes[now].r==-1) nodes[now].r=++idx;
        return qry(il,mid,l,r,nodes[now].l)+qry(mid+1,ir,l,r,nodes[now].r);
    }
    ll qry(int l,int r){return qry(1,1e9,l,r,1);}
}t;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int m;cin>>m;
    int now=0;
    nodes[1].l=nodes[1].r=-1;
    while(m--){
        int opr,x,y;cin>>opr>>x>>y;
        if(opr==1){
            int tmp=t.qry(x+now,y+now);
            cout<<tmp<<'\n';
            now=tmp;
        }
        else t.upd(x+now,y+now);
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…