Submission #1059211

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1059211	2024-08-14T18:50:41 Z	manhlinh1501	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	331 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 1e5 + 5;
const int oo32 = 1e9 + 5;

#define left ___left
#define right ___right

int Q, C = 0;

struct node {
    int sum = 0, lazy = 0;
    node *child[2] = {nullptr, nullptr};
};

void down(node *cur, int l, int r) {
    if(cur == nullptr or cur -> lazy == 0) return;
    if(l != r) {

        if(cur -> child[0] == nullptr) (cur -> child[0]) = new node();
        if(cur -> child[1] == nullptr) (cur -> child[1]) = new node();

        (cur -> child[0] -> lazy) = (cur -> lazy);
        (cur -> child[1] -> lazy) = (cur -> lazy);
    }
    (cur -> sum) = (cur -> lazy) * (r - l + 1);
    (cur -> lazy) = 0;
}

void add(node *cur, int l, int r, int u, int v) {
    down(cur, l, r);
    if(r < u or l > v) return;
    if(u <= l and r <= v) {
        (cur -> lazy) = 1;
        down(cur, l, r);
        return;
    }
    int m = (l + r) / 2;

    if((cur -> child[0]) == nullptr) (cur -> child[0]) = new node();
    if((cur -> child[1]) == nullptr) (cur -> child[1]) = new node();

    add(cur -> child[0], l, m, u, v);
    add(cur -> child[1], m + 1, r, u, v);

    (cur -> sum) = (cur -> child[0] -> sum) + (cur -> child[1] -> sum);
}

int get(node *cur, int l, int r, int u, int v) {
    down(cur, l, r);
    if(cur == nullptr or r < u or l > v) return 0;
    if(u <= l and r <= v) return (cur -> sum);
    int m = (l + r) / 2;
    int res = 0;
    if(cur -> child[0] != nullptr)
        res += get(cur -> child[0], l, m, u, v);
    if(cur -> child[1] != nullptr)
        res += get(cur -> child[1], m + 1, r, u, v);
    return res;
}

node *root = new node();

signed main() {
#define TASK "code"

    if (fopen(TASK ".inp", "r")) {
        freopen(TASK ".inp", "r", stdin);
        freopen(TASK ".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> Q;

    while(Q--) {
        int type, l, r;
        cin >> type >> l >> r;
        l += C;
        r += C;
        if(type == 2) {
            add(root, 1, oo32, l, r);
//            cerr << l << " " << r << " " << get(root, 1, oo32, l, r) << "\n";
        } else {
            C = get(root, 1, oo32, l, r);
            cout << C << "\n";
        }
    }

    return (0 ^ 0);
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(TASK ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         freopen(TASK ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	5960 KB	Output is correct
5	Correct	11 ms	7256 KB	Output is correct
6	Correct	11 ms	7060 KB	Output is correct
7	Correct	12 ms	7252 KB	Output is correct
8	Correct	87 ms	52348 KB	Output is correct
9	Correct	183 ms	89172 KB	Output is correct
10	Correct	190 ms	99784 KB	Output is correct
11	Correct	202 ms	108372 KB	Output is correct
12	Correct	199 ms	112016 KB	Output is correct
13	Correct	191 ms	139216 KB	Output is correct
14	Correct	189 ms	140372 KB	Output is correct
15	Correct	328 ms	254548 KB	Output is correct
16	Correct	320 ms	256684 KB	Output is correct
17	Correct	212 ms	145236 KB	Output is correct
18	Correct	198 ms	145520 KB	Output is correct
19	Correct	324 ms	262144 KB	Output is correct
20	Correct	331 ms	262144 KB	Output is correct