Submission #984489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984489	2024-05-16T17:38:49 Z	ivaziva	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	472 ms	262144 KB

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[40*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()
{
    ios_base::sync_with_stdio(false);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    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;
            ans=query(1,x+ans,y+ans);
            cout<<ans<<endl;
        }
        else
        {
            long long x,y;cin>>x>>y;
            update(1,x+ans,y+ans);
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	188244 KB	Output is correct
2	Correct	63 ms	188240 KB	Output is correct
3	Correct	62 ms	188180 KB	Output is correct
4	Correct	76 ms	188452 KB	Output is correct
5	Correct	78 ms	188488 KB	Output is correct
6	Correct	78 ms	188364 KB	Output is correct
7	Correct	85 ms	188496 KB	Output is correct
8	Correct	182 ms	189268 KB	Output is correct
9	Correct	335 ms	190300 KB	Output is correct
10	Correct	340 ms	190364 KB	Output is correct
11	Correct	327 ms	190292 KB	Output is correct
12	Correct	336 ms	190448 KB	Output is correct
13	Runtime error	472 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-