답안 #703858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
703858 2023-02-28T17:33:20 Z mihai145 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
373 ms 165792 KB
//
// 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;
}
# 결과 실행 시간 메모리 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