Submission #984456

#	Time	Username	Problem	Language	Result	Execution time	Memory
984456		ivaziva	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	118 ms	262144 KiB

apple

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100010

struct Segmentno{
    long long levodete=-1;
    long long desnodete=-1;
    long long levagranica;
    long long desnagranica;
    long long suma=0;
    long long lazy=0;
};

long long m;
Segmentno seg[64*MAXN];
long long cnt=2;

void push(long long node)
{
    if (seg[node].lazy==0) return;
    seg[node].suma+=seg[node].desnagranica-seg[node].levagranica+1;
    long long mid=(seg[node].levagranica+seg[node].desnagranica)/2;
    if (seg[node].levodete==-1)
    {
        seg[node].levodete=cnt;cnt++;
        seg[seg[node].levodete].levagranica=seg[node].levagranica;
        seg[seg[node].levodete].desnagranica=mid;
    }
    if (seg[node].desnodete==-1)
    {
        seg[node].desnodete=cnt;cnt++;
        seg[seg[node].desnodete].levagranica=mid+1;
        seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
    }
    seg[seg[node].levodete].lazy=1;
    seg[seg[node].desnodete].lazy=1;
    seg[node].lazy=0;
}

void update(long long node,long long l,long long r)
{
    push(node);
    if (l==seg[node].levagranica and r==seg[node].desnagranica) {seg[node].lazy=1;push(node);}
    else
    {
        long long mid=(seg[node].levagranica+seg[node].desnagranica)/2;
        if (seg[node].levodete==-1)
        {
            seg[node].levodete=cnt;cnt++;
            seg[seg[node].levodete].levagranica=seg[node].levagranica;
            seg[seg[node].levodete].desnagranica=mid;
        }
        if (seg[node].desnodete==-1)
        {
            seg[node].desnodete=cnt;cnt++;
            seg[seg[node].desnodete].levagranica=mid+1;
            seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
        }
        if (l>mid) update(seg[node].desnodete,l,r);
        else if (r<=mid) update(seg[node].levodete,l,r);
        else
        {
            update(seg[node].levodete,l,mid);
            update(seg[node].desnodete,mid+1,r);
        }
        push(seg[node].levodete);
        push(seg[node].desnodete);
        seg[node].suma=seg[seg[node].levodete].suma+seg[seg[node].desnodete].suma;
    }
}

long long query(long long node,long long l,long long r)
{
    push(node);
    if (l==seg[node].levagranica and r==seg[node].desnagranica) return seg[node].suma;
    long long mid=(seg[node].levagranica+seg[node].desnagranica)/2;
    if (seg[node].levodete==-1)
    {
        seg[node].levodete=cnt;cnt++;
        seg[seg[node].levodete].levagranica=seg[node].levagranica;
        seg[seg[node].levodete].desnagranica=mid;
    }
    if (seg[node].desnodete==-1)
    {
        seg[node].desnodete=cnt;cnt++;
        seg[seg[node].desnodete].levagranica=mid+1;
        seg[seg[node].desnodete].desnagranica=seg[node].desnagranica;
    }
    if (l>mid) return query(seg[node].desnodete,l,r);
    else if (r<=mid) return query(seg[node].levodete,l,r);
    else return query(seg[node].levodete,l,mid)+query(seg[node].desnodete,mid+1,r);
}

int main()
{
    cin>>m;
    seg[1].levagranica=1;
    seg[1].desnagranica=1000000000;
    seg[1].suma=0,seg[1].lazy=0;
    long long ans=0;
    for (long long z=0;z<m;z++)
    {
        long long t;cin>>t;
        if (t==1)
        {
            long long x,y;cin>>x>>y;
            long long ans1=query(1,x+ans,y+ans);
            cout<<ans1<<endl;ans=ans1;
        }
        else
        {
            long long x,y;cin>>x>>y;
            update(1,x+ans,y+ans);
        }
    }
}

• Subtask 1: 0 / 100