oj.uz

Submission #523457

# Submission time Handle Problem Language Result Execution time Memory
523457 2022-02-07T16:43:29 Z tmn2005 Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
 404 ms 188576 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
 
const int N = 123456;
const double eps = 1e-11;
const int inf = (int) 1e9;
const int mod = (int) 1e9 + 7;
 
struct tree {
    int sum, add, tl, tr, l, r;
    tree () : sum (0), add (0), l (-1), r (-1) {}
};
 
int cnt = 2;
tree t[64 * N];
 
void push (int v) {
    if (t[v].add) {
        t[v].sum = t[v].tr - t[v].tl + 1;
        int tm = (t[v].tl + t[v].tr) >> 1;
        if (t[v].l == -1) {
            t[v].l = cnt++;
            t[t[v].l].tl = t[v].tl;
            t[t[v].l].tr = tm;
        }
        if (t[v].r == -1) {
            t[v].r = cnt++;
            t[t[v].r].tl = tm + 1;
            t[t[v].r].tr = t[v].tr;
        }
        t[t[v].l].add = t[t[v].r].add = 1;
        t[v].add = 0;
    }
}
 
void update (int v, int l, int r) {
    push (v);
    if (l == t[v].tl && r == t[v].tr) {
        t[v].add = 1;
        push (v);
    } else {
        int tm = (t[v].tl + t[v].tr) >> 1;
        if (t[v].l == -1) {
            t[v].l = cnt++;
            t[t[v].l].tl = t[v].tl;
            t[t[v].l].tr = tm;
        }
        if (t[v].r == -1) {
            t[v].r = cnt++;
            t[t[v].r].tl = tm + 1;
            t[t[v].r].tr = t[v].tr;
        }
        if (l > tm) {
            update (t[v].r, l, r);
        } else if (r <= tm) {
            update (t[v].l, l, r);
        } else {
            update (t[v].l, l, tm);
            update (t[v].r, tm + 1, r);
        }
        push (t[v].l);
        push (t[v].r);
        t[v].sum = t[t[v].l].sum + t[t[v].r].sum;
    }
}
 
int get (int v, int l, int r) {
    push (v);
    if (l == t[v].tl && r == t[v].tr) {
        return t[v].sum;
    } else {
        int tm = (t[v].tl + t[v].tr) >> 1;
        if (t[v].l == -1) {
            t[v].l = cnt++;
            t[t[v].l].tl = t[v].tl;
            t[t[v].l].tr = tm;
        }
        if (t[v].r == -1) {
            t[v].r = cnt++;
            t[t[v].r].tl = tm + 1;
            t[t[v].r].tr = t[v].tr;
        }
        if (l > tm) {
            return get (t[v].r, l, r);
        } else if (r <= tm) {
            return get (t[v].l, l, r);
        } else {
            return get (t[v].l, l, tm) + get (t[v].r, tm + 1, r);
        }
    }
}
 
int main()
{
    int q;
    scanf ("%d", &q);
    t[1].sum = 0; t[1].add = 0;
    t[1].tl = 1; t[1].tr = inf;
    int c = 0;
    while (q--) {
        int d, x, y;
        scanf ("%d %d %d", &d, &x, &y);
        if (d == 1) {
            printf ("%d\n", c = get (1, x + c, y + c));
        } else {
            update (1, x + c, y + c);
        }
    }
    return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:102:11: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf ("%d", &q);
      |     ~~~~~~^~~~~~~~~~
apple.cpp:108:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf ("%d %d %d", &d, &x, &y);
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 185732 KB Output is correct
2 Correct 77 ms 185740 KB Output is correct
3 Correct 88 ms 185692 KB Output is correct
4 Correct 94 ms 185796 KB Output is correct
5 Correct 89 ms 185792 KB Output is correct
6 Correct 90 ms 185756 KB Output is correct
7 Correct 91 ms 185744 KB Output is correct
8 Correct 237 ms 186028 KB Output is correct
9 Correct 345 ms 186112 KB Output is correct
10 Correct 338 ms 186252 KB Output is correct
11 Correct 325 ms 187876 KB Output is correct
12 Correct 361 ms 187888 KB Output is correct
13 Correct 284 ms 188356 KB Output is correct
14 Correct 294 ms 188364 KB Output is correct
15 Correct 404 ms 188564 KB Output is correct
16 Correct 397 ms 188576 KB Output is correct
17 Correct 351 ms 188336 KB Output is correct
18 Correct 331 ms 188292 KB Output is correct
19 Correct 397 ms 188468 KB Output is correct
20 Correct 396 ms 188556 KB Output is correct