제출 #918731

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
918731		AndrijaM	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	71 ms	262144 KiB

apple

#include <bits/stdc++.h>

using namespace std;

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

void prop(long long pos,long long l,long long r)
{
    if(!pos || lz[pos]==0)
    {
        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(long long i,long long j,long long l,long long r,long long val,long long 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 ;
    }
    long long 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]];
}

long long query(long long i,long long j,long long l,long long r,long long 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];
    }
    long long 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--){
        long long 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