Submission #498996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
498996	2021-12-27T02:00:32 Z	gozonite	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	547 ms	207672 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	292 KB	Output is correct
4	Correct	26 ms	4864 KB	Output is correct
5	Correct	27 ms	6000 KB	Output is correct
6	Correct	27 ms	5768 KB	Output is correct
7	Correct	26 ms	5924 KB	Output is correct
8	Correct	195 ms	44532 KB	Output is correct
9	Correct	363 ms	77244 KB	Output is correct
10	Correct	395 ms	85480 KB	Output is correct
11	Correct	372 ms	91556 KB	Output is correct
12	Correct	375 ms	94456 KB	Output is correct
13	Correct	369 ms	109972 KB	Output is correct
14	Correct	356 ms	110932 KB	Output is correct
15	Correct	540 ms	201760 KB	Output is correct
16	Correct	547 ms	203068 KB	Output is correct
17	Correct	363 ms	114784 KB	Output is correct
18	Correct	417 ms	114920 KB	Output is correct
19	Correct	504 ms	207672 KB	Output is correct
20	Correct	530 ms	207648 KB	Output is correct