Submission #399276

#	Time	Username	Problem	Language	Result	Execution time	Memory
399276		snasibov05	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	384 ms	137300 KiB

apple

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define double long double
#define ull unsigned long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define s second
#define f first
#define pb push_back
#define oo 1000000000000000000ll

struct node{
    int sum;
    bool lazy;
    node* left;
    node* right;

    node(){
        sum = 0;
        lazy = false;
        left = nullptr;
        right = nullptr;
    }

    void update_sum(){
        sum = 0;
        if (left != nullptr) sum += left->sum;
        if (right != nullptr) sum += right->sum;
    }

    void push(int tl, int tr){
        if (!lazy) return;
        if (left == nullptr) left = new node();
        if (right == nullptr) right = new node();

        int tm = (tl + tr) / 2;
        left->sum = tm - tl + 1;
        left->lazy = true;

        right->sum = tr - tm;
        right->lazy = true;
        
        lazy = false;
    }
};

void update(node* v, int tl, int tr, int l, int r){
    if (tl == l && tr == r){
        v->sum = r - l + 1;
        v->lazy = true;
        return;
    }

    v->push(tl, tr);

    int tm = (tl + tr) / 2;
    if (l <= tm){
        if (v->left == nullptr) v->left = new node();
        update(v->left, tl, tm, l, min(r, tm));
    }
    if (r > tm){
        if (v->right == nullptr) v->right = new node();
        update(v->right, tm+1, tr, max(tm+1, l), r);
    }

    v->update_sum();
}

int getSum(node* v, int tl, int tr, int l, int r){
    if (tl == l && tr == r){
        return v->sum;
    }

    v->push(tl, tr);

    int tm = (tl + tr) / 2;
    int res = 0;

    if (l <= tm && v->left != nullptr) res += getSum(v->left, tl, tm, l, min(r, tm));
    if (r > tm && v->right != nullptr) res += getSum(v->right, tm+1, tr, max(l, tm+1), r);

    return res;
}

void solve() {
    const int nmax = 1e9;
    int c = 0;
    int m; cin >> m;

    node* t = new node();

    for (int i = 0; i < m; ++i) {
        int type, l, r; cin >> type >> l >> r;
        l += c; r += c;
        if (type == 1){
            c = getSum(t, 1, nmax, l, r);
            cout << c << "\n";
        } else update(t, 1, nmax, l, r);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tst; tst = 1;
    //cin >> tst;
    while (tst--){
        solve();
    }

    return 0;

}

• Subtask 1: 100 / 100