Submission #872806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
872806	2023-11-13T20:35:33 Z	AndreiBOTO	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	429 ms	232684 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)
{
    propag(aint,st,dr);
    if(st>b || dr<a)
        return ;
    if(a<=st && dr<=b)
    {
        aint->lazy=true;
        propag(aint,st,dr);
        return ;
    }
    else
    {
        int mij=st+dr;
        mij/=2;
        if(aint->left==NULL)
            aint->left=new SegTree();
        if(aint->right==NULL)
            aint->right=new SegTree();
        //if(a<=mij)
            update(aint->left,st,mij,a,b);
        //if(mij<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;
        if(a<=mij)
            kon+=query(aint->left,st,mij,a,b);
        if(mij<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	600 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	14 ms	5496 KB	Output is correct
5	Correct	14 ms	6492 KB	Output is correct
6	Correct	13 ms	6236 KB	Output is correct
7	Correct	13 ms	6616 KB	Output is correct
8	Correct	118 ms	47272 KB	Output is correct
9	Correct	214 ms	80976 KB	Output is correct
10	Correct	241 ms	90444 KB	Output is correct
11	Correct	249 ms	97648 KB	Output is correct
12	Correct	252 ms	100980 KB	Output is correct
13	Correct	227 ms	123220 KB	Output is correct
14	Correct	260 ms	124736 KB	Output is correct
15	Correct	429 ms	225872 KB	Output is correct
16	Correct	422 ms	227488 KB	Output is correct
17	Correct	240 ms	129104 KB	Output is correct
18	Correct	244 ms	129108 KB	Output is correct
19	Correct	414 ms	232592 KB	Output is correct
20	Correct	412 ms	232684 KB	Output is correct