Submission #864374

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
864374	2023-10-22T16:10:37 Z	anhphant	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	211 ms	208488 KB

apple

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'

ll M;

struct Node {
    ll L, R, sum, lazy, ls, rs;
};
Node ST[15000007];
ll cnt = 1;

struct DYNAMIC_SEGMENT_TREE {
     DYNAMIC_SEGMENT_TREE() {
        ST[1] = {1, ll(1e9), 0, 0, -1, -1};
     }

     void f(ll id) {
        ST[id].sum = ST[id].R - ST[id].L + 1;
        ST[id].lazy = 1;
     }

     void push_down(ll id) {
        ll MID = (ST[id].L + ST[id].R) / 2;
        if (ST[id].ls == -1) {
            ST[id].ls = ++cnt;
            ST[cnt] = {ST[id].L, MID, 0, 0, -1, -1};
        }
        if (ST[id].rs == -1) {
            ST[id].rs = ++cnt;
            ST[cnt] = {MID + 1, ST[id].R, 0, 0, -1, -1};
        }

        if (ST[id].lazy == 0) return;
        f(ST[id].ls);
        f(ST[id].rs);
        ST[id].lazy = 0;
     }

     void push_up(ll id) {
        ll MID = (ST[id].L + ST[id].R) / 2;
        if (ST[id].ls == -1) {
            ST[id].ls = ++cnt;
            ST[cnt] = {ST[id].L, MID, 0, 0, -1, -1};
        }
        if (ST[id].rs == -1) {
            ST[id].rs = ++cnt;
            ST[cnt] = {MID + 1, ST[id].R, 0, 0, -1, -1};
        }

        ST[id].sum = ST[ST[id].ls].sum + ST[ST[id].rs].sum;
     }

     void update(ll id, ll L, ll R) {
        if (ST[id].R < L || R < ST[id].L) return;
        //cerr << "update : " << id << " " << ST[id].L << " " << ST[id].R << endl;
        if (L <= ST[id].L && ST[id].R <= R) {
            f(id);
            return;
        }

        push_down(id);
        update(ST[id].ls, L, R);
        update(ST[id].rs, L, R);
        push_up(id);
     }

     ll getans(ll id, ll L, ll R) {
        if (ST[id].R < L || R < ST[id].L) return 0;
        if (L <= ST[id].L && ST[id].R <= R) return ST[id].sum;
        push_down(id);
        return getans(ST[id].ls, L, R) + getans(ST[id].rs, L, R);
     }

     void debug() {

     }
};

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0); cerr.tie(0);
    if (fopen("FILE.INP", "r")) {
        freopen("FILE.INP", "r", stdin);
        freopen("FILE.OUT", "w", stdout);
    }

    cin >> M;
    DYNAMIC_SEGMENT_TREE St;

    ll C = 0;
    for(int _ = 1; _ <= M; ++_) {
        ll D, L, R;
        cin >> D >> L >> R;
        if (D == 2) {
            St.update(1, L + C, R + C);
        }
        else {
            C = St.getans(1, L + C, R + C);
            cout << C << endl;
        }
        //cerr << "query " << _ << endl;
        //St.debug();
        //cerr << endl;
    }
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	8 ms	6800 KB	Output is correct
5	Correct	10 ms	6812 KB	Output is correct
6	Correct	10 ms	6748 KB	Output is correct
7	Correct	10 ms	6808 KB	Output is correct
8	Correct	68 ms	43808 KB	Output is correct
9	Correct	155 ms	76908 KB	Output is correct
10	Correct	152 ms	84972 KB	Output is correct
11	Correct	155 ms	91216 KB	Output is correct
12	Correct	162 ms	93188 KB	Output is correct
13	Correct	134 ms	109924 KB	Output is correct
14	Correct	135 ms	109632 KB	Output is correct
15	Correct	202 ms	202140 KB	Output is correct
16	Correct	198 ms	204212 KB	Output is correct
17	Correct	137 ms	116036 KB	Output is correct
18	Correct	137 ms	116052 KB	Output is correct
19	Correct	205 ms	208488 KB	Output is correct
20	Correct	211 ms	208352 KB	Output is correct