Submission #984515

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
984515	2024-05-16T17:59:03 Z	ivaziva	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 ms	47480 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

#define MAXN 100010

struct Segmentno{
    long long levodete,desnodete;
    long long levagranica,desnagranica;
    long long suma,lazy;
    Segmentno():suma(0),lazy(0),levodete(-1),desnodete(-1){}
};

long long m;
Segmentno seg[10*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);
        }
    }
}

Compilation message

apple.cpp: In constructor 'Segmentno::Segmentno()':
apple.cpp:11:20: warning: 'Segmentno::lazy' will be initialized after [-Wreorder]
   11 |     long long suma,lazy;
      |                    ^~~~
apple.cpp:9:15: warning:   'long long int Segmentno::levodete' [-Wreorder]
    9 |     long long levodete,desnodete;
      |               ^~~~~~~~
apple.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     Segmentno():suma(0),lazy(0),levodete(-1),desnodete(-1){}
      |     ^~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	47192 KB	Output is correct
2	Correct	7 ms	47196 KB	Output is correct
3	Correct	7 ms	47192 KB	Output is correct
4	Correct	20 ms	47452 KB	Output is correct
5	Correct	32 ms	47196 KB	Output is correct
6	Correct	30 ms	47196 KB	Output is correct
7	Correct	23 ms	47452 KB	Output is correct
8	Execution timed out	2051 ms	47480 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-