Submission #984506

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

apple

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-finline")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-fno-stack-protector")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-funroll-loops")
#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[30*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	55 ms	141344 KB	Output is correct
2	Correct	41 ms	141092 KB	Output is correct
3	Correct	40 ms	141140 KB	Output is correct
4	Correct	55 ms	141140 KB	Output is correct
5	Correct	60 ms	141140 KB	Output is correct
6	Correct	60 ms	141656 KB	Output is correct
7	Correct	52 ms	141316 KB	Output is correct
8	Correct	167 ms	141396 KB	Output is correct
9	Correct	315 ms	141764 KB	Output is correct
10	Execution timed out	2684 ms	262144 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-