Submission #790528

#	Time	Username	Problem	Language	Result	Execution time	Memory
790528		Blagoj	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1602 ms	150492 KiB

apple

#include <bits/stdc++.h>
#include <fstream>

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

ifstream fin("f.in");
ofstream fout("f.out");

struct Node {
    int sum, lazy, tl, tr, l, r;
    Node() : sum(0), lazy(0), l(-1), r(-1) {}
} tree[64 * 100005];

int cnt = 1;

void push(int k) {
    if (tree[k].lazy) {
        tree[k].sum = tree[k].tr - tree[k].tl + 1;
        int m = (tree[k].tl + tree[k].tr) / 2; 
        if (tree[k].l == -1) {
            tree[k].l = ++cnt;
            tree[cnt].tl = tree[k].tl;
            tree[cnt].tr = m;
        }
        if (tree[k].r == -1) {
            tree[k].r = ++cnt;
            tree[cnt].tl = m + 1;
            tree[cnt].tr = tree[k].tr;
        }
        tree[tree[k].l].lazy = tree[tree[k].r].lazy = 1;
        tree[k].lazy = 0;
    }
}

void update(int k, int i, int j) {
    push(k);
    if (tree[k].tr < i || tree[k].tl > j) return;
    if (i <= tree[k].tl && tree[k].tr <= j) {
        tree[k].lazy = 1;
        push(k);
        return;
    }
    int m = (tree[k].tl + tree[k].tr) / 2;
    if (tree[k].l == -1) {
        tree[k].l = ++cnt;
        tree[cnt].tl = tree[k].tl;
        tree[cnt].tr = m;
    }
    if (tree[k].r == -1) {
        tree[k].r = ++cnt;
        tree[cnt].tl = m + 1;
        tree[cnt].tr = tree[k].tr;
    }
    update(tree[k].l, i, j);
    update(tree[k].r, i, j);
    tree[k].sum = tree[tree[k].l].sum + tree[tree[k].r].sum;
}

ll query(int k, int i, int j) {
    push(k);
    if (tree[k].tr < i || tree[k].tl > j) return 0;
    if (i <= tree[k].tl && tree[k].tr <= j) return tree[k].sum;
    int m = (tree[k].tl + tree[k].tr) / 2;
    if (tree[k].l == -1) {
        tree[k].l = ++cnt;
        tree[cnt].tl = tree[k].tl;
        tree[cnt].tr = m;
    }
    if (tree[k].r == -1) {
        tree[k].r = ++cnt;
        tree[cnt].tl = m + 1;
        tree[cnt].tr = tree[k].tr;
    }
    return query(tree[k].l, i, j) + query(tree[k].r, i, j);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    fin >> q;
    int c = 0;
    tree[1].sum = tree[1].lazy = 0;
    tree[1].tl = 1;
    tree[1].tr = 1e9;
    while (q--) {
        int d, x, y;
        fin >> d >> x >> y;
        if (d == 1) {
            c = query(1, x + c, y + c);
            fout << c << endl;
        }
        else update(1, x + c, y + c);
    }
}

• Subtask 1: 0 / 100