제출 #1330004

#제출 시각아이디문제언어결과실행 시간메모리
1330004ahmetlbktd4Monkey and Apple-trees (IZhO12_apple)C++20
100 / 100
251 ms137432 KiB
#include "bits/stdc++.h"
using namespace std;

const int N = 1e9;

struct node {
    int s;
    bool lazy;
    node *le,*ri;
    node() : s(0), lazy(0), le(nullptr), ri(nullptr) {}
};

void push(node* v,int l,int r){
    if (!v || !v->lazy || l == r)
    return;
    int m = (l+r) >> 1;
    if (!v->le)
    v->le = new node();
    if (!v->ri)
    v->ri = new node();
    v->le->s = m-l+1;
    v->ri->s = r-m;
    v->le->lazy = 1;
    v->ri->lazy = 1;
    v->lazy = 0;
}

void upd(node* &v,int l,int r,int x,int y){
    if (y < l || x > r)
    return;
    if (!v)
    v = new node();
    if (x <= l && r <= y){
        v->s = r-l+1;
        v->lazy = 1;
        return;
    }
    push(v,l,r);
    int m = (l+r)>>1;
    upd(v->le,l,m,x,y);
    upd(v->ri,m+1,r,x,y);
    int ls = 0,rs = 0;
    if (v->le)
    ls = v->le->s;
    if (v->ri)
    rs = v->ri->s;
    v->s = ls+rs;
}

int jem(node* v,int l,int r,int x,int y){
    if (!v || y < l || r < x)
    return 0;
    if (x <= l && y >= r)
    return v->s;
    push(v,l,r);
    int m = (l+r) >> 1;
    return jem(v->le,l,m,x,y)+jem(v->ri,m+1,r,x,y);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int q;
    cin >> q;
    node* v = nullptr; 
    int c = 0;
    while (q--){
        int d,x,y;
        cin >> d >> x >> y;
        x += c;
        y += c;
        if (d == 1){
            c = jem(v,1,N,x,y);
            cout << c << "\n";
        }    
        else upd(v,1,N,x,y);
    } 
}
#Verdict Execution timeMemoryGrader output
Fetching results...