Submission #1000917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000917		coolboy19521	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	216 ms	111172 KiB

apple

#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"

#define int int

using namespace std;

const int sz = 8e6 + 36;
const int md = 1e9 + 7;

int st[sz], lz[sz], l[sz], r[sz];
int tr = 1;
bool f;

void relax(int v, int le, int ri) {
    st[v] = lz[v] * (ri - le + 1);
    if (le != ri) {
        if (!l[v]) l[v] = ++ tr;
        if (!r[v]) r[v] = ++ tr;
        lz[l[v]] = lz[v];
        lz[r[v]] = lz[v];
    }
    lz[v] = 0;
}

void update(int le, int ri, int ql, int qr, int v) {
    if (le > qr || ri < ql) return;
    if (ql <= le && ri <= qr) {
        lz[v] = 1;
        relax(v, le, ri);
        return;
    }
    int mi = le + (ri - le) / 2;
    if (ql <= mi) {
        if (!l[v]) l[v] = ++ tr;
        update(le, mi, ql, qr, l[v]);
    }
    if (mi <= qr) {
        if (!r[v]) r[v] = ++ tr;
        update(mi + 1, ri, ql, qr, r[v]);
    }
    st[v] = max(st[v], st[l[v]] + st[r[v]]);
}

int query(int le, int ri, int ql, int qr, int v) {
    if(lz[v]) relax(v, le, ri);
    if (le > qr || ri < ql) return 0;
    if (ql <= le && ri <= qr) return st[v];
    int mi = le + (ri - le) / 2;
    int lq = l[v] ? query(le, mi, ql, qr, l[v]) : 0;
    int rq = r[v] ? query(mi + 1, ri, ql, qr, r[v]) : 0;
    return lq + rq;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int m;
    cin >> m;

    int c = 0, n = 1e9 + 100;

    while (m --) {
        int t, a, b;
        cin >> t >> a >> b;
        a += c, b += c;
        if (2 == t) {
            // if (a == 7) f = true;
            // cout << "UPD " << a << ' ' << b << ": ";
            f = false;
            update(1, n, a, b, 1);
            // cout << a << ' ' << b << ' ' << query(1, n, a, b, 1) << '\n';
            // cout << "FULL " << query(1, n, 1, n, 1) << '\n';
        } else {
            // cout << "QUERY " << a << ' ' << b << ": ";
            int r = query(1, n, a, b, 1);
            // cout << "QUERY " << r << '\n';
            cout << r << '\n';
            c = r;
        }

        // for (int i = 1; i <= 10; i ++) {
        //     cout << query(1, n, i, i, 1) << ' ';
        // }
        // cout << '\n';
        // cout << "FULL " << query(1, n, 1, n, 1) << '\n';
    }
}

• Subtask 1: 100 / 100