Submission #872815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
872815	2023-11-13T20:51:02 Z	AndreiBOTO	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	478 ms	231784 KB

apple

#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

///Hey I heard you like the wild ones
///Wild Ones - Flo Rida, Sia

using namespace std;

const int INF=1e9;

struct SegTree{
    public:
    int s;
    bool lazy;
    SegTree *left;
    SegTree *right;

    SegTree()
    {
        s=0;
        lazy=false;
        left=right=NULL;
    }
};

void propag(SegTree *aint,int st,int dr)
{
    if(aint==NULL)
        return ;
    else
    {
        if(aint->lazy)
        {
            aint->s=dr-st+1;
            if(st!=dr)
            {
                if(aint->left==NULL)
                    aint->left=new SegTree();
                if(aint->right==NULL)
                    aint->right=new SegTree();
                aint->left->lazy=true;
                aint->right->lazy=true;
            }
            aint->lazy=false;
        }
    }
}

void update(SegTree *aint,int st,int dr,int a,int b)
{
    if(aint==NULL)
        return ;
    propag(aint,st,dr);
    if(st>b || dr<a)
        return ;
    if(a<=st && dr<=b)
    {
        aint->lazy=true;
        aint->s=dr-st+1;
        return ;
    }
    else
    {
        int mij=st+dr;
        mij/=2;
        if(aint->left==NULL)
            aint->left=new SegTree();
        if(aint->right==NULL)
            aint->right=new SegTree();
        update(aint->left,st,mij,a,b);
        update(aint->right,mij+1,dr,a,b);
        aint->s=(aint->left->s)+(aint->right->s);
    }
}

int query(SegTree *aint,int st,int dr,int a,int b)
{
    if(aint==NULL || st>b || dr<a)
        return 0;
    propag(aint,st,dr);
    if(a<=st && dr<=b)
        return aint->s;
    else
    {
        int kon=0;
        int mij=st+dr;
        mij/=2;
        kon+=query(aint->left,st,mij,a,b);
        kon+=query(aint->right,mij+1,dr,a,b);
        return kon;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    SegTree *aint=new SegTree();
    int t,c=0;
    cin>>t;
    while(t--)
    {
        int type,x,y;
        cin>>type>>x>>y;
        if(type==1)
        {
            c=query(aint,1,INF,x+c,y+c);
            cout<<c<<"\n";
        }
        else
            update(aint,1,INF,x+c,y+c);
    }
    return 0;
}

Compilation message

apple.cpp:3: warning: ignoring '#pragma optimize GCC' [-Wunknown-pragmas]
    3 | #pragma optimize GCC ("Ofast")
      |

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	356 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	11 ms	5328 KB	Output is correct
5	Correct	14 ms	6232 KB	Output is correct
6	Correct	14 ms	6232 KB	Output is correct
7	Correct	19 ms	6228 KB	Output is correct
8	Correct	116 ms	46676 KB	Output is correct
9	Correct	231 ms	79132 KB	Output is correct
10	Correct	250 ms	88676 KB	Output is correct
11	Correct	253 ms	96072 KB	Output is correct
12	Correct	289 ms	99100 KB	Output is correct
13	Correct	244 ms	121088 KB	Output is correct
14	Correct	253 ms	122696 KB	Output is correct
15	Correct	478 ms	223788 KB	Output is correct
16	Correct	451 ms	225240 KB	Output is correct
17	Correct	273 ms	128160 KB	Output is correct
18	Correct	289 ms	128356 KB	Output is correct
19	Correct	464 ms	231784 KB	Output is correct
20	Correct	462 ms	231744 KB	Output is correct