Submission #947803

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
947803	2024-03-17T03:45:55 Z	THXuan	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	299 ms	262144 KB

apple

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
ll t[4 * MAXN], lazy[4 * MAXN], lf[4*MAXN], rg[4*MAXN];
int node_count = 1;

int create_node() {
    node_count++;
    return node_count;
}

void pushdown(int v, int l, int r) {
    int tm = (l + r) / 2;
    if (lf[v] == 0) lf[v] = create_node();
    if (rg[v] == 0) rg[v] = create_node();
    if (lazy[v]) {
        lazy[lf[v]] = 1;
        lazy[rg[v]] = 1;
        t[lf[v]] =  (tm - l + 1);
        t[rg[v]] = (r - tm);
        lazy[v] = 0;
    }
}
void upd(int v, int l, int r, int tl, int tr, ll val) {
    if (l > r)return;
    if (l == tl && r == tr) {
        lazy[v] = val;
        t[v] = (r - l + 1);
        return;
    }
    pushdown(v, tl, tr);
    int tm = (tl + tr) / 2;
    if (r <= tm) {
        if (lf[v] == 0) lf[v] = create_node();
        upd(lf[v], l, r, tl, tm, val);
    }
    else if (l >= tm + 1) {
        if (rg[v] == 0) rg[v] = create_node();
        upd(rg[v], l, r, tm + 1, tr, val);
    }
    else {
        if (lf[v] == 0) lf[v] = create_node();
        if (rg[v] == 0) rg[v] = create_node();
        upd(lf[v], l, tm, tl, tm, val);
        upd(rg[v], tm + 1, r, tm + 1, tr, val);
    }
    t[v] = t[lf[v]] + t[rg[v]] + lazy[v] * (tr - tl + 1);
}
ll query(int v, int tl, int tr, int l, int r) {
    if (l > r)return 0;
    if (l == tl && r == tr)return t[v];
    pushdown(v, tl, tr);
    int tm = (tl + tr) / 2;
    if (r <= tm)return query(lf[v], tl, tm, l, r);
    else if (l > tm)return query(rg[v], tm + 1, tr, l, r);
    else {
        ll left = query(lf[v], tl, tm, l, tm);
        ll right = query(rg[v], tm + 1, tr, tm + 1, r);
        return left + right;
    }
}

void solve()
{
    int m; cin >> m;
    int c = 0;
    while (m--) {
        int type; cin >> type;
        int l, r; cin >> l >> r;
        if (type == 1) {
            c = query(1, 1, 1000000005, l + c, r + c);
            cout << c << "\n";
        }
        else {
            upd(1, l + c, r + c, 1, 1000000005, 1);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;// cin>>t;
    while (t--) solve();
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	8 ms	5468 KB	Output is correct
5	Correct	12 ms	7384 KB	Output is correct
6	Correct	9 ms	7512 KB	Output is correct
7	Correct	9 ms	7404 KB	Output is correct
8	Correct	69 ms	32080 KB	Output is correct
9	Correct	154 ms	53844 KB	Output is correct
10	Correct	168 ms	59272 KB	Output is correct
11	Correct	153 ms	62068 KB	Output is correct
12	Correct	163 ms	65152 KB	Output is correct
13	Correct	144 ms	74608 KB	Output is correct
14	Correct	141 ms	76452 KB	Output is correct
15	Runtime error	299 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-