Submission #918725

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
918725	2024-01-30T10:02:03 Z	AndrijaM	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	44 ms	188248 KB

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)
    {
        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>r)
    {
        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>r)
    {
        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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	188240 KB	Output is correct
2	Correct	43 ms	188248 KB	Output is correct
3	Incorrect	43 ms	188240 KB	Output isn't correct
4	Halted	0 ms	0 KB	-