Submission #399276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
399276	2021-05-05T13:56:18 Z	snasibov05	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	384 ms	137300 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	13 ms	3308 KB	Output is correct
5	Correct	17 ms	4024 KB	Output is correct
6	Correct	15 ms	3916 KB	Output is correct
7	Correct	16 ms	3916 KB	Output is correct
8	Correct	115 ms	29196 KB	Output is correct
9	Correct	238 ms	50604 KB	Output is correct
10	Correct	247 ms	55956 KB	Output is correct
11	Correct	249 ms	60104 KB	Output is correct
12	Correct	255 ms	62056 KB	Output is correct
13	Correct	236 ms	72204 KB	Output is correct
14	Correct	236 ms	72832 KB	Output is correct
15	Correct	378 ms	133412 KB	Output is correct
16	Correct	378 ms	134212 KB	Output is correct
17	Correct	248 ms	75736 KB	Output is correct
18	Correct	242 ms	75428 KB	Output is correct
19	Correct	373 ms	137300 KB	Output is correct
20	Correct	384 ms	137284 KB	Output is correct