Submission #1317480

#TimeUsernameProblemLanguageResultExecution timeMemory
1317480rahanhematinejadMonkey and Apple-trees (IZhO12_apple)C++20
0 / 100
0 ms332 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define fi first
#define se second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define mt make_tuple
#define mp make_pair
#define all(x) (x).begin(), (x).end()

const int N = 1e5 + 10;
const int LG = 32;
const int INF = 1e9 + 10;
const ll LL_INF = 1e18 + 10;
const ll MOD1 = 1e9 + 7;
const ll MOD2 = 998244353;
const int MAXN = 1e9 + 10, MAXV = 1e6 + 10;

int q, Num = 0, C = 0;

struct Node{
    int cnt, sz, L, R;
    bool lazy;

    Node (int cnt = 0, int sz = 0, int L = -1, int R = -1, bool lazy = 0){
        this -> cnt = cnt;
        this -> sz = sz;
        this -> L = L;
        this -> R = R;
        this -> lazy = lazy;
    }

    void Upd(){
        cnt = sz;
        lazy = 1;
    }
    void Shift(Node &n1, Node &n2){
        if(!lazy){
            return;
        }
        n1.Upd();
        n2.Upd();
        lazy = 0;
    }
    void Merge(Node &n1, Node &n2){
        sz = n1.sz + n2.sz;
        cnt = n1.cnt + n2.cnt;
    }
};
vector<Node> seg;

int Left(int id){
    if(seg[id].L != -1){
        return seg[id].L;
    }
    seg[id].L = ++Num;
    seg.push_back(Node (0, seg[id].sz >> 1));
    return Num;
}
int Right(int id){
    if(seg[id].R != -1){
        return seg[id].R;
    }
    seg[id].R = ++Num;
    seg.push_back(Node (0, (seg[id].sz >> 1) + (seg[id].sz & 1)));
    return Num;
}

void shift(int id){
    seg[id].Shift(seg[Left(id)], seg[Right(id)]);
}
void merge(int id){
    seg[id].Merge(seg[Left(id)], seg[Right(id)]);
}
void update(int l, int r, int st = 0, int en = MAXN, int id = 0){
    if(st >= r || en <= l){
        return;
    }
    if(st >= l && en <= r){
        seg[id].Upd();
        return;
    }
    shift(id);
    int mid = (st + en) >> 1;
    update(l, r, st, mid, Left(id));
    update(l, r, mid, en, Right(id));
    merge(id);
}
int get(int l, int r, int st = 0, int en = MAXN, int id = 0){
    if(st >= r || en <= l){
        return 0;
    }
    if(st >= l && en <= r){
        return seg[id].cnt;
    }
    shift(id);
    int mid = (st + en) >> 1;
    return get(l, r, st, mid, Left(id)) + get(l, r, mid, en, Right(id));
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> q;
    seg.push_back(Node (0, MAXN));
    while(q--){
        int t, l, r;
        cin >> t >> l >> r;
        --l;
        if(t == 1){
            auto val = get(l + C, r + C);
            cout << val << '\n';
            C += val;
        }
        else{
            update(l + C, r + C);
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...