Submission #1178315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178315		kokoue	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	411 ms	290420 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 extendleft(Node *node)
{
    if(node->left==nullptr && node->l!=node->r)
    {
        int mid=(node->l+node->r)/2;
        node->left=new Node();
        node->left->l=node->l;
        node->left->r=mid;
        node->left->lazy=node->lazy;
    }
}
void extendright(Node *node)
{
    if(node->right==nullptr && node->l!=node->r)
    {
        int mid=(node->l+node->r)/2;
        node->right=new Node();
        node->right->l=mid+1;
        node->right->r=node->r;
        node->right->lazy=node->lazy;
    }
}
void extend(Node *node)
{
    extendleft(node);
    extendright(node);
   // printf("out of extend\n");
}
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)
{
  //  printf("in update %d %d\n",node->l,node->r);
  //pushLazy(node);
    if(ur<node->l || node->r<ul) return;
    pushLazy(node);
    if(ul<=node->l && node->r<=ur)
    {
       // printf("doing hole with %d %d\n",node->l,node->r);
        node->cntr=node->r-node->l+1;

        extend(node);
        if(node->l!=node->r)
        {
            node->left->lazy=1;
            node->right->lazy=1;
        }
       // printf("finishing whole %d %d\n",node->l,node->r);
        return;
    }
    int mid=(node->l+node->r)/2;
    if(ul<=mid) extendleft(node);
    if(ur>mid) extendright(node);
    if(node->left!=nullptr) update(ul,ur,node->left);
    if(node->right!=nullptr) update(ul,ur,node->right);
    if(node->lazy) return;
    node->cntr=0;
    if(node->left!=nullptr)
    {
        if(node->left->lazy) node->cntr+=node->left->r-node->left->l+1;
        else node->cntr+=node->left->cntr;
    }
    if(node->right!=nullptr)
    {
        if(node->right->lazy) node->cntr+=node->right->r-node->right->l+1;
        else node->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)
    {
        if(node->lazy) return node->r-node->l+1;
        return node->cntr;
    }
    int mid=(node->l+node->r)/2;
    if(ql<=mid) extendleft(node);
    if(qr>mid) extendright(node);
    int ans=0;
    if(node->left!=nullptr) ans+=query(ql,qr,node->left);
    if(node->right!=nullptr) ans+=query(ql,qr,node->right);
    return ans;
}
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("in query %d\n",i);
        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);

        }
    }
}
/*
3
2 5 8
2 7 10
1 1 10
*/

• Subtask 1: 0 / 100