Submission #703859

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
703859	2023-02-28T17:34:15 Z	mihai145	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	358 ms	153720 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 LG = 30;
const int NMAX = LG * 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	68 ms	152908 KB	Output is correct
2	Correct	68 ms	152940 KB	Output is correct
3	Correct	68 ms	152852 KB	Output is correct
4	Correct	77 ms	152848 KB	Output is correct
5	Correct	79 ms	152920 KB	Output is correct
6	Correct	80 ms	152984 KB	Output is correct
7	Correct	85 ms	153008 KB	Output is correct
8	Correct	159 ms	153092 KB	Output is correct
9	Correct	263 ms	153248 KB	Output is correct
10	Correct	285 ms	153320 KB	Output is correct
11	Correct	270 ms	153220 KB	Output is correct
12	Correct	277 ms	153292 KB	Output is correct
13	Correct	275 ms	153384 KB	Output is correct
14	Correct	254 ms	153432 KB	Output is correct
15	Correct	327 ms	153720 KB	Output is correct
16	Correct	321 ms	153424 KB	Output is correct
17	Correct	286 ms	153544 KB	Output is correct
18	Correct	288 ms	153340 KB	Output is correct
19	Correct	358 ms	153332 KB	Output is correct
20	Correct	328 ms	153436 KB	Output is correct