제출 #1341933

#제출 시각아이디문제언어결과실행 시간메모리
1341933vjudge1Monkey and Apple-trees (IZhO12_apple)C++20
100 / 100
257 ms113032 KiB
#include <bits/stdc++.h> //  +
using namespace std;     // +++
#define inf 1e18         //  +
#define all(a) a.begin(), a.end()
void files() {
}

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 n;
    cin >> n;

    int c = 0;
    for (int i = 0; i < n; ++i) {
        int t, l, r;
        cin >> t >> l >> r;
        l += c, r += c;
        if (t == 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), files();
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...