Submission #1000917

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000917	2024-06-18T11:17:17 Z	coolboy19521	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	216 ms	111172 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4440 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	7 ms	4188 KB	Output is correct
5	Correct	10 ms	7860 KB	Output is correct
6	Correct	9 ms	8024 KB	Output is correct
7	Correct	8 ms	8028 KB	Output is correct
8	Correct	67 ms	26964 KB	Output is correct
9	Correct	123 ms	40500 KB	Output is correct
10	Correct	141 ms	44972 KB	Output is correct
11	Correct	137 ms	47572 KB	Output is correct
12	Correct	136 ms	50004 KB	Output is correct
13	Correct	149 ms	58964 KB	Output is correct
14	Correct	123 ms	60208 KB	Output is correct
15	Correct	192 ms	107092 KB	Output is correct
16	Correct	193 ms	108884 KB	Output is correct
17	Correct	135 ms	62140 KB	Output is correct
18	Correct	130 ms	62304 KB	Output is correct
19	Correct	205 ms	110372 KB	Output is correct
20	Correct	216 ms	111172 KB	Output is correct