Submission #1340306

#TimeUsernameProblemLanguageResultExecution timeMemory
1340306vjudge1Monkey and Apple-trees (IZhO12_apple)C++20
100 / 100
296 ms113044 KiB
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
const int MX = 1e9 , N = 1e5+5 , SZ = N * 100;
struct Node {
    int val{};
    Node() {}
    Node(int x) : val(x) {}
};

Node seg[SZ];
int L[SZ],R[SZ];
bool lazy[SZ];
int root = 1;

Node merge(Node l , Node r) {
    Node ret;
    ret.val = l.val + r.val;
    return ret;
}

void extend(int l , int r , int node) {
    if (l == r) return;
    if (!L[node]) {
        L[node] = ++root;
        R[node] = ++root;
    }
}

void propagate(int l , int r , int node) {
    if (!lazy[node]) return;
    seg[node] = r - l + 1;
    if (l != r) lazy[L[node]] = lazy[R[node]] = true;
    lazy[node] = false;
}

void update(int l , int r , int node, int lq , int rq) {
    extend(l,r,node);
    propagate(l,r,node);
    if (l > rq or r < lq) return;
    if (l >= lq and r <= rq) {
        lazy[node] = true;
        propagate(l,r,node);
        return;
    }
    int mid = l + r >> 1;
    update(l,mid,L[node],lq,rq);
    update(mid+1,r,R[node],lq,rq);
    seg[node] = merge(seg[L[node]],seg[R[node]]);
}

Node query(int l , int r , int node , int lq , int rq) {
    extend(l,r,node);
    propagate(l,r,node);
    if (l > rq or r < lq) return 0;
    if (l >= lq and r <= rq) return seg[node];
    int mid = l + r >> 1;
    return merge(query(l,mid,L[node],lq,rq),query(mid+1,r,R[node],lq,rq));
}

void update(int l , int r) {
    update(1,MX,1,l,r);
}

int query(int l , int r) {
    return query(1,MX,1,l,r).val;
}


void solve() {
    int m; cin >> m;
    int c = 0;
    while (m--) {
        int d,x,y; cin >> d >> x >> y;
        int l = x + c;
        int r = y + c;
        if (l > r) swap(l,r);
        if (d == 1) {
            c = query(l,r);
            cout << c << '\n';
        }
        else update(l,r);
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...