Submission #872806

#	Time	Username	Problem	Language	Result	Execution time	Memory
872806		AndreiBOTO	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	429 ms	232684 KiB

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 (stderr)

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

• Subtask 1: 100 / 100