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
#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;
}
# 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