Submission #314466

#	Time	Username	Problem	Language	Result	Execution time	Memory
314466		Vince729	Monkey and Apple-trees (IZhO12_apple)	C++11	100 / 100	51 ms	3096 KiB

apple

#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;

typedef long long ll;

const int MAXN = 100003;
const int MOD = 1000000007;

struct Node {
    int l, r, sum;
    bool z;
    Node *ln, *rn;

    Node(int _l, int _r): l(_l), r(_r), sum(0), z(0), ln(nullptr), rn(nullptr) {}

    void upd(int a, int b) {
        if (z) return;
        if (a <= l && b >= r) {
            sum = r-l+1;
            z = true;
        } else {
            int mid = (l+r)/2;
            if (a <= mid) {
                if (!ln) ln = new Node(l, mid);
                ln->upd(a, b);
            }
            if (b > mid) {
                if (!rn) rn = new Node(mid+1, r);
                rn->upd(a, b);
            }
            sum = 0;
            if (ln) sum += ln->sum;
            if (rn) sum += rn->sum;
        }
    }

    int qry(int a, int b) {
        if (b < l || a > r) return 0;
        if (a <= l && b >= r) return sum;
        if (z) return min(b, r)-max(a, l)+1;
        int ret = 0;
        if (ln) ret += ln->qry(a, b);
        if (rn) ret += rn->qry(a, b);
        return ret;
    }
};

int m;
Node root(1, 1000000000);

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> m;
    int c = 0;
    while (m--) {
        int d, x, y; cin >> d >> x >> y;
        if (d == 2) {
            root.upd(x+c, y+c);
        } else {
            c = root.qry(x+c, y+c);
            cout << c << '\n';
        }
    }
}

• Subtask 1: 100 / 100