Submission #1178304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178304		kokoue	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	398 ms	327680 KiB

apple

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const ll maxn =1e9;
int m;
struct Node
{
    int cntr=0;
    bool lazy=0;
    int l,r;
    Node *left=nullptr;
    Node *right=nullptr;
};
Node *root;
void extend(Node *node)
{
    if(node->left==nullptr && node->l!=node->r)
    {
        int mid=(node->l+node->r)/2;
        node->left=new Node();
        node->right=new Node();
        node->left->l=node->l;
        node->left->r=mid;
        node->right->l=mid+1;
        node->right->r=node->r;
        node->left->lazy=node->right->lazy=node->lazy;
    }
}
void pushLazy(Node *node)
{
    if(node->lazy)
    {
        node->cntr=node->r-node->l+1;
        extend(node);
        if(node->l!=node->r)
        {
            node->left->lazy=1;
            node->right->lazy=1;
        }
        node->lazy=0;
    }
}
void update(int ul,int ur,Node *node)
{
    pushLazy(node);
    if(ur<node->l || node->r<ul) return;
   // pushLazy(node);
    if(ul<=node->l && node->r<=ur)
    {
        node->cntr=node->r-node->l+1;
        //printf("%d %d\n",node->l,node->r);
        extend(node);
        if(node->l!=node->r)
        {
            node->left->lazy=1;
            node->right->lazy=1;
        }
        return;
    }
    extend(node);
    update(ul,ur,node->left);
    update(ul,ur,node->right);
    node->cntr=node->left->cntr+node->right->cntr;
}
int query(int ql,int qr,Node *node)
{
    pushLazy(node);
    if(qr<node->l || node->r<ql) return 0;
    //pushLazy(node);
    if(ql<=node->l && node->r<=qr)
    {
       // printf("return hole %d %d\n",node->l,node->r);
        return node->cntr;
    }
    extend(node);
    return query(ql,qr,node->left)+query(ql,qr,node->right);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>m;
    root=new Node();
    root->l=1;
    root->r=maxn;
    ll c=0;
    for(int i=0;i<m;i++)
    {
        //printf("checking root:  %d\n",root->cntr);
        int t,x,y;
        cin>>t>>x>>y;
        if(t==1)
        {
            c=query(x+c,y+c,root);
            cout<<c<<"\n";

        }
        if(t==2)
        {
            update(x+c,y+c,root);
           /* for(int j=x+c;j<=y+c;j++)
            {
                printf("query %d: %d\n",j,query(j,j,root));
            }*/
           // printf("checking %d\n",query(x+c,y+c,root));
        }
    }
}

• Subtask 1: 0 / 100