Submission #864377

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
864377	2023-10-22T16:19:55 Z	anhphant	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	219 ms	206316 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;

    void AddNode(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};
        }
    }

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

     void push_down(ll id) {
        AddNode(id);
        if (ST[id].lazy == 0) return;
        f(ST[id].ls);
        f(ST[id].rs);
        ST[id].lazy = 0;
     }

     void push_up(ll id) {
        AddNode(id);
        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;
        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() {
        for(int id = 1; id <= cnt; ++id) {
            cerr << "i = " << id << " : " << ST[id].L << " " << ST[id].R << " " << ST[id].sum << " " << ST[id].lazy
                << " " << ST[id].ls << " " << ST[id].rs << endl;
        }
     }


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;
    ST[1] = {1, ll(1e9), 0, 0, -1, -1};

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

        //cerr << "query " << _ << endl;
        //debug();
        //cerr << endl;
    }
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	6828 KB	Output is correct
5	Correct	10 ms	6748 KB	Output is correct
6	Correct	10 ms	6748 KB	Output is correct
7	Correct	10 ms	6748 KB	Output is correct
8	Correct	67 ms	43784 KB	Output is correct
9	Correct	149 ms	76688 KB	Output is correct
10	Correct	151 ms	85004 KB	Output is correct
11	Correct	154 ms	91216 KB	Output is correct
12	Correct	161 ms	93268 KB	Output is correct
13	Correct	140 ms	109652 KB	Output is correct
14	Correct	136 ms	109652 KB	Output is correct
15	Correct	199 ms	199964 KB	Output is correct
16	Correct	198 ms	202176 KB	Output is correct
17	Correct	136 ms	113876 KB	Output is correct
18	Correct	136 ms	113744 KB	Output is correct
19	Correct	219 ms	206316 KB	Output is correct
20	Correct	195 ms	206112 KB	Output is correct