Submission #703858

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
703858	2023-02-28T17:33:20 Z	mihai145	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	373 ms	165792 KB

apple

//
// Created by mihai145 on 28.02.2023.
// Test problem: https://oj.uz/problem/view/IZhO12_apple
//

#include <iostream>

using namespace std;

const int NMAX = 32 * 100000;

class DynamicSegmentTree {
private:
    int kNodes, v[4 * NMAX];
    pair<int, int> sons[4 * NMAX];
    bool lazy[4 * NMAX];

    void init(int idx) {
        sons[idx].first = ++kNodes;
        sons[idx].second = ++kNodes;
    }

    void push(int idx, int l, int r) {
        if (lazy[idx]) {
            v[idx] = r - l + 1;
            lazy[sons[idx].first] = true;
            lazy[sons[idx].second] = true;
        }
    }

public:
    void Init() {
        for (int i = 1; i < 4 * NMAX; i++) {
            v[i] = 0;
            sons[i].first = -1, sons[i].second = -1;
            lazy[i] = false;
        }
        kNodes = 1;
    }

    void Update(int idx, int l, int r, int ql, int qr) {
        if (sons[idx].first == -1) {
            init(idx);
        }

        push(idx, l, r);

        if (r < ql || qr < l) return;
        if (ql <= l && r <= qr) {
            lazy[idx] = true;
            push(idx, l, r);
            return;
        }

        int mid = (l + r) >> 1;
        Update(sons[idx].first, l, mid, ql, qr);
        Update(sons[idx].second, mid + 1, r, ql, qr);
        v[idx] = v[sons[idx].first] + v[sons[idx].second];
    }

    int Query(int idx, int l, int r, int ql, int qr) {
        if (sons[idx].first == -1) {
            init(idx);
        }

        push(idx, l, r);

        if (r < ql || qr < l) return 0;
        if (ql <= l && r <= qr) return v[idx];

        int mid = (l + r) >> 1;
        int a1 = Query(sons[idx].first, l, mid, ql, qr), a2 = Query(sons[idx].second, mid + 1, r, ql, qr);
        return a1 + a2;
    }
};
DynamicSegmentTree dst;

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

    dst.Init();

    int m; cin >> m;
    int d, x, y, c = 0;

    for (int i = 1; i <= m; i++) {
        cin >> d >> x >> y;
        x += c, y += c;
        if (d == 1) {
            c = dst.Query(1, 1, 1e9, x, y);
            cout << c << '\n';
        } else {
            dst.Update(1, 1, 1e9, x, y);
        }
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	77 ms	163012 KB	Output is correct
2	Correct	70 ms	163052 KB	Output is correct
3	Correct	75 ms	163084 KB	Output is correct
4	Correct	80 ms	163068 KB	Output is correct
5	Correct	91 ms	163152 KB	Output is correct
6	Correct	86 ms	163096 KB	Output is correct
7	Correct	86 ms	163148 KB	Output is correct
8	Correct	168 ms	163276 KB	Output is correct
9	Correct	278 ms	165188 KB	Output is correct
10	Correct	291 ms	165240 KB	Output is correct
11	Correct	284 ms	165308 KB	Output is correct
12	Correct	290 ms	165236 KB	Output is correct
13	Correct	279 ms	165684 KB	Output is correct
14	Correct	268 ms	165648 KB	Output is correct
15	Correct	373 ms	165696 KB	Output is correct
16	Correct	333 ms	165684 KB	Output is correct
17	Correct	298 ms	165572 KB	Output is correct
18	Correct	279 ms	165572 KB	Output is correct
19	Correct	356 ms	165792 KB	Output is correct
20	Correct	333 ms	165684 KB	Output is correct