Submission #523457

#	Time	Username	Problem	Language	Result	Execution time	Memory
523457		tmn2005	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	404 ms	188576 KiB

apple

#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 (stderr)

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 / 100