Submission #498996

#	Time	Username	Problem	Language	Result	Execution time	Memory
498996		gozonite	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	547 ms	207672 KiB

apple

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
using namespace std;
using ll = long long;

struct Node {
    int sum, lazy, l, r;
    Node *ln, *rn;
    Node(int tl, int tr) : sum(0), lazy(0), l(tl), r(tr), ln(nullptr), rn(nullptr) {}
};

int M;
Node* tree;

void pushup(Node* n) {
    n->sum = n->ln->sum + n->rn->sum;
}
void pushdown(Node* n) {
    int l = n->l, r = n->r;
    int mid = (l+r)/2;
    if (n->ln == nullptr) n->ln = new Node(l, mid);
    if (n->rn == nullptr) n->rn = new Node(mid+1, r);

    if (n->lazy == 0) return;
    n->ln->sum = n->lazy*(n->ln->r - n->ln->l + 1);
    n->rn->sum = n->lazy*(n->rn->r - n->rn->l + 1);
    n->ln->lazy = n->lazy; n->rn->lazy = n->lazy;
    n->lazy = 0;
}
void setr(int a, int b, int v, Node* n) {
    int l = n->l, r = n->r;
    if (r < a || b < l) return;
    if (a <= l && r <= b) {
        n->sum = v*(r-l+1);
        n->lazy = v;
    } else {
        pushdown(n);
        setr(a, b, v, n->ln);
        setr(a, b, v, n->rn);
        pushup(n);
    }
}
int sumr(int a, int b, Node* n) {
    int l = n->l, r = n->r;
    if (r < a || b < l) return 0;
    if (a <= l && r <= b) return n->sum;
    pushdown(n);
    return sumr(a, b, n->ln) + sumr(a, b, n->rn);
}

int main() {
    cin >> M;
    int C = 0;
    tree = new Node(1, 1e9);
    for (int i = 1; i <= M; i++) {
        int D, X, Y; cin >> D >> X >> Y;
        if (D==1) {
            C = sumr(X+C, Y+C, tree);
            cout << C << endl;

        } else {
            setr(X+C, Y+C, 1, tree);
        }
    }

    return 0;
}

• Subtask 1: 100 / 100