제출 #1197385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197385		Godgift42	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	151 ms	313324 KiB

apple

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1000000009;

vector<int> l(20000000,0);
vector<int> r(20000000,0);
vector<int> st(20000000,0);
vector<int> lz(20000000,0);
int nodes=1;

void psh(int v,int tl,int tr,int tm){
    if(!lz[v])return;
    st[l[v]]=tm-tl+1;
    st[r[v]]=tr-tm;
    lz[l[v]]=1;
    lz[r[v]]=1;
    lz[v]=0;
}

void upd(int v, int tl, int tr,int left, int right){
    if(tl==left and tr==right){
        st[v]=(right-left+1);
        lz[v]=1;
        return;
    }
    if(l[v]==0){
        nodes++;
        l[v]=nodes;
    }
    if(r[v]==0){
        nodes++;
        r[v]=nodes;
    }
    int tm=(tl+tr)/2;
    psh(v,tl,tr,tm);
    if(tm>=right)upd(l[v],tl,tm,left,right);
    else if(left>tm)upd(r[v],tm+1,tr,left,right);
    else{
        upd(l[v],tl,tm,left,tm);
        upd(r[v],tm+1,tr,tm+1,right);
    }
    st[v] = st[l[v]] + st[r[v]];
}

int sm(int v, int tl, int tr,int left, int right){
    if(tl==left and tr==right){
        return st[v];
    }
    if(l[v]==0){
        nodes++;
        l[v]=nodes;
    }
    if(r[v]==0){
        nodes++;
        r[v]=nodes;
    }
    int tm=(tl+tr)/2;
    psh(v,tl,tr,tm);
    if(tm>=right)return sm(l[v],tl,tm,left,right);
    else if(left>tm)return sm(r[v],tm+1,tr,left,right);
    else{
        return sm(l[v],tl,tm,left,tm)+sm(r[v],tm+1,tr,tm+1,right);
    }
}


int main(){
    int m;
    cin >> m;
    int cur=0;
    while(m--){
        int k;
        cin >> k;
        int x,y;
        cin >> x >> y;
        if(k==1){
            cur=sm(1,1,MAXN,x+cur,y+cur);
            cout << cur <<"\n";
        }
        else{
            upd(1,1,MAXN,x+cur,y+cur);
        }
    }
}
/*chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,Q,a[200005],st[20000005],l[2000   0005],r[20000005],Nodes = 1;

void update(int pos,int val,int v = 1,int start = 1,int end = 1e9)
{
    if(start==end)
    {
        st[v] += val;
        return;
    }
    if(l[v]==0)
        l[v] = ++Nodes;
    if(r[v]==0)
        r[v] = ++Nodes;
    int mid = (start + end)/2;
    if(pos <= mid)
        update(pos,val,l[v],start,mid);
    else
        update(pos,val,r[v],mid+1,end);
    st[v] = st[l[v]] + st[r[v]];
}

int query(int left,int right,int v = 1,int start = 1,int end = 1e9)
{
    if(start==left && end==right)
        return st[v];
    if(l[v]==0)
        l[v] = ++Nodes;
    if(r[v]==0)
        r[v] = ++Nodes;
    int mid = (start + end)/2;
    if(right <= mid)
        return query(left,right,l[v],start,mid);
    else if(left > mid)
        return query(left,right,r[v],mid+1,end);
    else
        return query(left,mid,l[v],start,mid) + query(mid+1,right,r[v],mid+1,end);
}

int main()
{
    scanf("%d%d",&N,&Q);
    for(int i = 1 ; i <= N ; i++)
    {
        scanf("%d",&a[i]);
        update(a[i],1);
    }
    for(int x,y,i = 1 ; i <= Q ; i++)
    {
        char op;
        scanf(" %c%d%d",&op,&x,&y);
        if(op=='?')
            printf("%d\n",query(x,y));
        else
        {
            update(a[x],-1);
            a[x] = y;
            update(a[x],1);
        }    
    }
    return 0;
}*/

• Subtask 1: 0 / 100