Submission #1279182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279182		cpismayilmmdv985	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	260 ms	137540 KiB

apple

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int lchild = 0, rchild = 0, result = 0;
};

const int MXN = 200'005;
const int limit = 1000'000'005;
Node segtree[MXN * 60];
int last = 1, lazy[MXN * 60];

inline void createNode(const int &v) {
    if (segtree[v].lchild)  return;
    segtree[v].lchild = ++last, segtree[v].rchild = ++last;
    return;
}

void relax(int v, int tl, int tr) {
    if (!lazy[v])   return;
    segtree[v].result = tr - tl + 1;
    if (tl != tr) {
        createNode(v);
        lazy[segtree[v].lchild] = lazy[segtree[v].rchild] = 1;
    }
}

void update(int v, int tl, int tr, int l, int r) {
    relax(v, tl, tr);
    createNode(v);
    if (l > r || tl > r || l > tr || !v)  return;
    if (l <= tl && tr <= r) {
        lazy[v] = 1;
        relax(v, tl, tr);
        return;
    }
    int tm = (tl + tr) >> 1;
    update(segtree[v].lchild, tl, tm, l, min(r, tm));
    update(segtree[v].rchild, tm + 1, tr, max(l, tm + 1), r);
    segtree[v].result = segtree[segtree[v].lchild].result + segtree[segtree[v].rchild].result;
}

int getans(int v, int tl, int tr, int l, int r) {
    relax(v, tl, tr);
    createNode(v);
    if (l > r || tl > r || l > tr || !v)  return 0;
    if (l <= tl && tr <= r)         return segtree[v].result;
    int tm = (tl + tr) >> 1;
    return getans(segtree[v].lchild, tl, tm, l, min(r, tm)) + getans(segtree[v].rchild, tm + 1, tr, max(l, tm + 1), r);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int Q, T, L, R, C = 0;  cin >> Q;
    while (Q-- > 0) {
        cin >> T >> L >> R, L += C, R += C;
        if (T == 2) update(1, 1, limit, L, R);
        else {
            int res = getans(1, 1, limit, L, R); 
            cout << res << '\n';
            C = res;
        }
    }

    return 0;
}

• Subtask 1: 100 / 100