Submission #719334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
719334	2023-04-05T18:51:14 Z	Muaath_5	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	500 ms	262144 KB

apple

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e9+10;

struct segnode {
    int sum = 0;
    int upd = 0;
    segnode *segleft, *segright;
    segnode() : sum(0), upd(0), segleft(nullptr), segright(nullptr) {}
};

segnode* root;

void pushdown(segnode* node, int s, int e)
{
    if (node->upd != 1) return;

    const int mid = (s + e) / 2;

    if (!node->segleft && s < e)
        node->segleft = new segnode();
    if (s < e)
        node->segleft->upd = 1;

    if (!node->segright && s < e)
        node->segright = new segnode();
    if (s < e)
        node->segright->upd = 1;
    node->upd = 2;
    node->sum = (e - s + 1);
}

void lazy_update(segnode* node, int l, int r, int s=1, int e=N) {
    pushdown(node, s, e);
    if (e < l || s > r) return;
    if (l <= s && e <= r) {
        node->upd = max(node->upd, 1);
        pushdown(node, s, e);
        return;
    }
    const int mid = (s + e) / 2;

    if (!node->segleft && s < e)
        node->segleft = new segnode();
    if (!node->segright && s < e)
        node->segright = new segnode();

    int cur = 0;
    if (node->segleft) {
        lazy_update(node->segleft, l, r, s, mid);
        cur += node->segleft->sum;
    }
    if (node->segright) {
        lazy_update(node->segright, l, r, mid+1, e);
        cur += node->segright->sum;
    }
    node->sum = cur;
}

int query(segnode* node, int l, int r, int s=1, int e=N) {
    pushdown(node, s, e);
    if (e < l || s > r) return 0;
    if (l <= s && e <= r)
        return node->sum;
    const int mid = (s + e) / 2;
    int sum = 0;
    if (node->segleft)
        sum += query(node->segleft, l, r, s, mid);
    if (node->segright)
        sum += query(node->segright, l, r, mid+1, e);
    return sum;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int q, cmd, x, y;
    cin >> q;
    root = new segnode();
    int c = 0;
    while (q--) {
        cin >> cmd >> x >> y;
        if (cmd == 1) {
            c = query(root, x+c, y+c);
            cout << c << '\n';
        }
        else if (cmd == 2) {
            lazy_update(root, x+c, y+c);
        }
    }
}

Compilation message

apple.cpp: In function 'void pushdown(segnode*, int, int)':
apple.cpp:20:15: warning: unused variable 'mid' [-Wunused-variable]
   20 |     const int mid = (s + e) / 2;
      |               ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	13 ms	5844 KB	Output is correct
5	Correct	17 ms	6996 KB	Output is correct
6	Correct	15 ms	6740 KB	Output is correct
7	Correct	16 ms	7020 KB	Output is correct
8	Correct	135 ms	51536 KB	Output is correct
9	Correct	316 ms	87344 KB	Output is correct
10	Correct	283 ms	98020 KB	Output is correct
11	Correct	318 ms	106444 KB	Output is correct
12	Correct	308 ms	110140 KB	Output is correct
13	Correct	313 ms	136984 KB	Output is correct
14	Correct	307 ms	138236 KB	Output is correct
15	Correct	500 ms	254672 KB	Output is correct
16	Correct	488 ms	256688 KB	Output is correct
17	Correct	281 ms	145268 KB	Output is correct
18	Correct	290 ms	145356 KB	Output is correct
19	Correct	484 ms	262144 KB	Output is correct
20	Correct	490 ms	262144 KB	Output is correct