Submission #1270096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270096		newsboy	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	291 ms	205600 KiB

apple

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <utility>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

struct Node {
    i64 sum = 0;
    i64 set = 0;
    Node* l = nullptr;
    Node* r = nullptr;
};

struct DST {
    i64 n;
    DST() {}
    DST(i64 n) : n(n) {}
    Node* root = new Node;
    void apply(Node* t, i64 len, i64 set) {
        if (set == 1) {
            t->set = set;
            t->sum = len * set;
        }
    }
    void push(Node* t, i64 l, i64 r) {
        if (t->l == nullptr) {
            t->l = new Node;
        }
        if (t->r == nullptr) {
            t->r = new Node;
        }
        i64 m = (l + r) / 2;
        apply(t->l, m - l, t->set);
        apply(t->r, r - m, t->set);
    }
    i64 merge(i64 x, i64 y) {
        return x + y;
    }
    void rangeApply(Node* t, i64 l, i64 r, i64 x, i64 y, i64 v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(t, r - l, v);
            return;
        }
        push(t, l, r);
        i64 m = (l + r) / 2;
        rangeApply(t->l, l, m, x, y, v);
        rangeApply(t->r, m, r, x, y, v);
        t->sum = merge(t->l->sum, t->r->sum);
    }
    void rangeApply(i64 x, i64 y, i64 v) {
        rangeApply(root, 0, n, x, y, v);
    }
    i64 rangeQuery(Node* t, i64 l, i64 r, i64 x, i64 y) {
        if (l >= y || r <= x) {
            return 0;
        }
        if (l >= x && r <= y) {
            return t->sum;
        }
        push(t, l, r);
        i64 m = (l + r) / 2;
        return merge(rangeQuery(t->l, l, m, x, y), rangeQuery(t->r, m, r, x, y));
    }
    i64 rangeQuery(i64 x, i64 y) {
        return rangeQuery(root, 0, n, x, y);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i64 M;
    cin >> M;
    DST seg(1E9);
    i64 C = 0;
    for (i64 i = 0; i < M; i++) {
        i64 D, X, Y;
        cin >> D >> X >> Y;
        X--;
        if (D == 1) {
            C = seg.rangeQuery(X + C, Y + C);
            cout << C << '\n';
        }
        else {
            seg.rangeApply(X + C, Y + C, 1);
        }
    }
}

• Subtask 1: 100 / 100