oj.uz

Submission #382578

# Submission time Handle Problem Language Result Execution time Memory
382578 2021-03-27T19:05:25 Z JerryLiu06 Monkey and Apple-trees (IZhO12_apple) C++11
0 / 100
 552 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

struct Node { int sum = 0, l = -1, r = -1, tl, tr, lazy = 0; };

int M, C, timer = 2; Node tree[6000000];

void pushdown(int x) { int mid = (tree[x].tl + tree[x].tr) / 2;
    if (!tree[x].lazy) return ; tree[x].sum = tree[x].tr - tree[x].tl + 1; 
    
  //  cout << tree[x].l << " " << tree[x].r << endl;

    if (tree[x].tl < tree[x].tr) {
        if (tree[x].l == -1) { tree[x].l = timer++; tree[tree[x].l].tl = tree[x].tl; tree[tree[x].l].tr = mid; }
        if (tree[x].r == -1) { tree[x].r = timer++; tree[tree[x].r].tl = mid + 1; tree[tree[x].r].tr = tree[x].tr; }

        tree[tree[x].l].lazy = tree[tree[x].r].lazy = 1;
    }
    tree[x].lazy = 0;   
}
void update(int x, int l, int r) { int mid = (tree[x].tl + tree[x].tr) / 2;
    if (tree[x].tl > r || tree[x].tr < l) return ;

    pushdown(x); if (l <= tree[x].tl && tree[x].tr <= r) { tree[x].lazy = 1; return ; }
    
   // cout << tree[x].l << " " << tree[x].r << endl;
   
    if (tree[x].l == -1) { tree[x].l = timer++; tree[tree[x].l].tl = tree[x].tl; tree[tree[x].l].tr = mid; }
    if (tree[x].r == -1) { tree[x].r = timer++; tree[tree[x].r].tl = mid + 1; tree[tree[x].r].tr = tree[x].tr; }

    update(tree[x].l, l, r); update(tree[x].r, l, r); pushdown(tree[x].l); pushdown(tree[x].r); 
    
    tree[x].sum = tree[tree[x].l].sum + tree[tree[x].r].sum;
}
int query(int x, int l, int r) { int mid = (tree[x].tl + tree[x].tr) / 2;
    if (tree[x].tl > r || tree[x].tr < l) return 0;

    pushdown(x); if (l <= tree[x].tl && tree[x].tr <= r) return tree[x].sum;
    
    if (tree[x].l == -1) { tree[x].l = timer++; tree[tree[x].l].tl = tree[x].tl; tree[tree[x].l].tr = mid; }
    if (tree[x].r == -1) { tree[x].r = timer++; tree[tree[x].r].tl = mid + 1; tree[tree[x].r].tr = tree[x].tr; }

    return query(tree[x].l, l, r) + query(tree[x].r, l, r);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> M; tree[1].tl = 1; tree[1].tr = 1000000000;
    
    for (int i = 0; i < M; i++) { int D, X, Y; cin >> D >> X >> Y;

        if (D == 1) { C = query(1, X + C, Y + C); cout << C << "\n"; }

        if (D == 2) update(1, X + C, Y + C);
    }
}

Compilation message

apple.cpp: In function 'void pushdown(int)':
apple.cpp:10:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   10 |     if (!tree[x].lazy) return ; tree[x].sum = tree[x].tr - tree[x].tl + 1;
      |     ^~
apple.cpp:10:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   10 |     if (!tree[x].lazy) return ; tree[x].sum = tree[x].tr - tree[x].tl + 1;
      |                                 ^~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 141292 KB Output is correct
2 Correct 75 ms 141292 KB Output is correct
3 Correct 77 ms 141420 KB Output is correct
4 Correct 88 ms 141420 KB Output is correct
5 Correct 95 ms 141420 KB Output is correct
6 Correct 92 ms 141420 KB Output is correct
7 Correct 92 ms 141420 KB Output is correct
8 Correct 203 ms 141932 KB Output is correct
9 Correct 349 ms 142188 KB Output is correct
10 Correct 352 ms 142188 KB Output is correct
11 Correct 368 ms 142316 KB Output is correct
12 Correct 360 ms 142188 KB Output is correct
13 Correct 337 ms 142316 KB Output is correct
14 Correct 328 ms 142188 KB Output is correct
15 Runtime error 552 ms 262144 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -