Submission #918727

#	Time	Username	Problem	Language	Result	Execution time	Memory
918727		AndrijaM	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	45 ms	188248 KiB

apple

#include <bits/stdc++.h>

using namespace std;

const int maxn = (int)3e5+10;
int mx=1e9, st[maxn*40], lz[maxn*40];
int L[maxn*40], R[maxn*40], IND = 1, q,c;

void prop(int pos,int l,int r)
{
    if(!pos || lz[pos]!=1)
    {
        return ;
    }
    if(lz[pos]==1)
    {
        st[pos]=lz[pos]*(r-l+1);
        if(l!=r)
        {
            if(!L[pos])L[pos]=++IND;
            if(!R[pos])R[pos]=++IND;
            lz[L[pos]]=lz[R[pos]]=lz[pos];
        }
        lz[pos]=0;
    }
}

void u(int i,int j,int l,int r,int val,int pos)
{
    if(!pos || i>j)
    {
        return ;
    }
    if(i>r || j<l)
    {
        return ;
    }
    prop(pos,l,r);
	if(i<=l && r<=j)
    {
        st[pos]=(r-l+1)*val;
        if(l!=r)
        {
            if(!L[pos])L[pos]=++IND;
            if(!R[pos])R[pos]=++IND;
            lz[L[pos]]=lz[R[pos]]=val;
        }
        return ;
    }
    int mid=(l+r)/2;
    if(i<=mid)
    {
        if(!L[pos])L[pos]=++IND;
        u(i,j,l,mid,val,L[pos]);
    }
    if(j>mid)
    {
        if(!R[pos])R[pos]=++IND;
        u(i,j,mid+1,r,val,R[pos]);
    }
    st[pos]=st[L[pos]]+st[R[pos]];
}

int query(int i,int j,int l,int r,int pos)
{
    if(!pos || i>j)
    {
        return 0;
    }
    if(i>r || j<l)
    {
        return 0;
    }
	prop(pos,l,r);
	if(i<=l && r<=j)
    {
        return st[pos];
    }
    int mid=(l+r)/2;
    return query(i,j,l,mid,L[pos])+query(i,j,mid+1,r,R[pos]);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> q;
    memset(lz,0,sizeof(lz));
    memset(st,0,sizeof st);
    memset(L,0,sizeof L);
    memset(R,0,sizeof R);
    while(q--){
        int t, x, y; cin >> t >> x >> y; x+=c, y+=c;
        if(t==1) c = query(x,y,1,mx,1), cout << c <<endl;
        else u(x,y,1,mx,1,1);
    }
}

• Subtask 1: 0 / 100