제출 #1240709

#제출 시각아이디문제언어결과실행 시간메모리
1240709Malix원숭이와 사과 나무 (IZhO12_apple)C++20
0 / 100
1 ms324 KiB
#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,p,q;
    Node *l,*r;
    Node(int x,int y,int z):val(x),lazy(0),p(y),q(z),l(NULL),r(NULL){}
}*root;

void push(Node *&x){
    int m=(x->p+x->q)/2;
    if(x->l){
        x->l->val=m-x->p+1;
        x->l->lazy=1;
    }
    else x->l=new Node(m-x->p+1,x->p,m);
    if(x->r){
        x->r->val=x->q-m;
        x->r->lazy=1;
    }
    else x->r=new Node(x->q-m,m+1,x->q);
    x->lazy=0;
}

void update(Node *&x,int l,int r,int u,int v){
    if(u>v)return;
    if(!x)x=new Node(0,l,r);
    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));
    update(x->r,m+1,r,max(m+1,u),v);
    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){
    if(u>v||!x)return 0;
    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))+query(x->r,m+1,r,max(m+1,u),v);
}

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