Submission #864362

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
864362	2023-10-22T15:44:09 Z	anhphant	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	285 ms	262144 KB

apple

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

ll M;

struct DYNAMIC_SEGMENT_TREE {
     struct Node {
        ll L, R, sum, lazy, ls, rs;
     };
     vector<Node> ST;

     DYNAMIC_SEGMENT_TREE() {
        ST = {{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 = ST.size();
            ST.push_back({ST[id].L, MID, 0, 0, -1, -1});
        }
        if (ST[id].rs == -1) {
            ST[id].rs = ST.size();
            ST.push_back({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 = ST.size();
            ST.push_back({ST[id].L, MID, 0, 0, -1, -1});
        }
        if (ST[id].rs == -1) {
            ST[id].rs = ST.size();
            ST.push_back({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() {
        for(int i = 0; i < ST.size(); ++i) {
            cerr << "i = " << i << " : " << ST[i].L << " " << ST[i].R << " " << ST[i].sum << " "
                << ST[i].lazy << " " << ST[i].ls << " " << ST[i].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;
    DYNAMIC_SEGMENT_TREE St;

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

Compilation message

apple.cpp: In member function 'void DYNAMIC_SEGMENT_TREE::debug()':
apple.cpp:75:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<DYNAMIC_SEGMENT_TREE::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i = 0; i < ST.size(); ++i) {
      |                        ~~^~~~~~~~~~~
apple.cpp: In function 'int main()':
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.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("FILE.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

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	11 ms	7348 KB	Output is correct
5	Correct	13 ms	7884 KB	Output is correct
6	Correct	13 ms	7888 KB	Output is correct
7	Correct	15 ms	8260 KB	Output is correct
8	Correct	85 ms	51396 KB	Output is correct
9	Correct	196 ms	101052 KB	Output is correct
10	Correct	192 ms	101528 KB	Output is correct
11	Correct	183 ms	101040 KB	Output is correct
12	Correct	186 ms	101280 KB	Output is correct
13	Correct	184 ms	200312 KB	Output is correct
14	Correct	209 ms	201800 KB	Output is correct
15	Runtime error	285 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-