Submission #1240753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240753		Malix	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	266 ms	155108 KiB

apple

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

struct Node{
    int val,lazy,sz;
    Node *l,*r;
    Node(int x,int y):val(x),lazy(0),sz(y),l(NULL),r(NULL){}
}*root;

void push(Node *&x){
    if(x->l){
        x->l->val=x->l->sz;
        x->l->lazy=1;
    }
    if(x->r){
        x->r->val=x->r->sz;
        x->r->lazy=1;
    }
    x->lazy=0;
}

void update(Node *&x,int l,int r,int u,int v,bool f){
    if(u>v)return;
    if(!x){
        x=new Node(0,r-l+1);
        if(f){
            x->val=x->sz;
            x->lazy=1;
        }
    }
    if(l!=r&&x->lazy)push(x);
    if(l==u&&r==v){
        x->val=r-l+1;
        x->lazy=1;
        return;
    }
    int m=(l+r)/2;
    update(x->l,l,m,u,min(m,v),x->sz==x->val);
    update(x->r,m+1,r,max(m+1,u),v,x->sz==x->val);
    if(x->sz!=x->val)x->val=(x->l?x->l->val:0)+(x->r?x->r->val:0);
}

int query(Node *&x,int l,int r,int u,int v,bool f){
    if(u>v)return 0;
    if(!x){
        x=new Node(0,r-l+1);
        if(f){
            x->val=x->sz;
            x->lazy=1;
        }
    }
    if(l!=r&&x->lazy)push(x);
    if(l==u&&r==v)return x->val;
    int m=(l+r)/2;
    return query(x->l,l,m,u,min(m,v),x->sz==x->val)+query(x->r,m+1,r,max(m+1,u),v,x->sz==x->val);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int c=0;
    int q;cin>>q;
    root=new Node(0,inf);
    while(q--){
        int t,x,y;cin>>t>>x>>y;
        x+=c;y+=c;
        if(t==2)update(root,1,inf,x,y,0);
        else{
            c=query(root,1,inf,x,y,0);
            cout<<c<<"\n";
        }
    }
}

• Subtask 1: 100 / 100