Submission #635775

#TimeUsernameProblemLanguageResultExecution timeMemory
635775tvladm2009Monkey and Apple-trees (IZhO12_apple)C++14
0 / 100
0 ms212 KiB
#include <fstream>
#include <iostream>

using namespace std;

const int MAX_N = 1e5;
int aint[4 * MAX_N * 10 + 1];
bool lazy[4 * MAX_N * 10 + 1];

void push(int v, int l, int r) {
    if (lazy[v]) {
        int mid = (l + r) / 2;
        lazy[2 * v] = true;
        aint[2 * v] = mid - l + 1;
        lazy[2 * v + 1] = true;
        aint[2 * v + 1] = r - mid;
        lazy[v] = false;
    }
}

void update(int v, int l, int r, int p, int q) {
    if (p > q) {
        return;
    } else if (p <= l && r <= q) {
        aint[v] = r - l + 1;
        lazy[v] = true;
    } else {
        push(v, l, r);
        int mid = (l + r) / 2;
        update(2 * v, l, mid, p, min(mid, q));
        update(2 * v + 1, mid + 1, r, max(p, mid + 1), q);
        aint[v] = aint[2 * v] + aint[2 * v + 1];
    }
}

int query(int v, int l, int r, int p, int q) {
    if (p > q) {
        return 0;
    } else if (l == p && r == q) {
        return aint[v];
    } else {
        push(v, l, r);
        int mid = (l + r) / 2;
        return query(2 * v, l, mid, p, min(mid, q)) + query(2 * v + 1, mid + 1, r, max(p, mid + 1), q);
    }
}

int main() {
    ifstream fin("f.in");
    ofstream fout("f.out");
    int q;
    fin >> q;
    int c = 0;
    while (q--) {
        int t, x, y;
        fin >> t >> x >> y;
        if (t == 1) {
            c = query(1, 1, 20 * MAX_N, x + c, y + c);
            fout << c << "\n";
        } else {
            update(1, 1, 20 * MAX_N, x + c, y + c);
        }
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...