Submission #1143156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143156		SulA	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	420 ms	327680 KiB

apple

#include <bits/stdc++.h>
//#pragma GCC optimize("popcnt")
#define all(a) a.begin(), a.end()
using namespace std;
using namespace chrono;

struct node {
    int l, r, sum = 0, lazy = 0;
    node *lc = nullptr, *rc = nullptr;
    node(int l, int r) : l(l), r(r) {}
};

void create_kids(node *u) {
    if (u->l == u->r || u->lc != nullptr) return;
    int mid = (u->l + u->r)/2;
    u->lc = new node(u->l, mid);
    u->rc = new node(mid+1, u->r);
}
void propagate(node *u) {
    create_kids(u);
    if (u->lazy != 0) {
        u->sum = (u->r - u->l + 1) * u->lazy;
        if (u->l != u->r)
            u->lc->lazy = u->lazy, u->rc->lazy = u->lazy;
        u->lazy = 0;
    }
}
void update(node *u, int ul, int ur, int x = 1) {
    propagate(u);
    if (ul <= u->l && u->r <= ur) {
        u->lazy = x;
        propagate(u);
        return;
    }
    if (ur < u->l || u->r < ul) return;
    create_kids(u);
    update(u->lc, ul, ur, x);
    update(u->rc, ul, ur, x);
    u->sum = u->lc->sum + u->rc->sum;
}
int query(node *u, int ql, int qr) {
    propagate(u);
    if (ql <= u->l && u->r <= qr) return u->sum;
    if (qr < u->l || u->r < ql) return 0;
    return query(u->lc, ql, qr) +
           query(u->rc, ql, qr);
}

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

    int n, c = 0; cin>>n;
    node* segtree = new node(0, 1'000'000'003);
    while (n--) {
        int t,l,r; cin>>t>>l>>r;
        l += c, r += c;
        if (t == 1) {
            c = query(segtree, l, r);
            cout << c << '\n';
        } else {
            update(segtree, l, r);
        }
    }
}

• Subtask 1: 0 / 100