Submission #339792

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
339792	2020-12-26T08:23:41 Z	Vladikus004	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	522 ms	207812 KB

apple

#include <bits/stdc++.h>
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

struct node{
    int sum, tl, tr, mod;
    node *l, *r;
    node(){
        sum = 0; tl = tr = mod = -1;
        l = r = nullptr;
    }
    node(int L, int R, int SUM){
        sum = SUM; tl = L; tr = R;
        mod = -1;
        l = r = nullptr;
    }
};

const int SZ = (int)1e9+3;
node *root = new node(0, SZ, 0);

void push(node *v){
    if (v->tl == v->tr) return;
    int tm = (v->tl + v->tr) / 2;
    if (!v->l)
        v->l = new node(v->tl, tm, 0);
    if (!v->r)
        v->r = new node(tm + 1, v->tr, 0);
    if (v->mod != -1){
        v->l->mod = v->mod;
        v->r->mod = v->mod;
        v->l->sum = (v->l->tr - v->l->tl + 1) * (v->mod);
        v->r->sum = (v->r->tr - v->r->tl + 1) * (v->mod);
        v->mod = -1;
    }
}

void up(node *v, int l, int r, int val){
    if (l > r) return;
    if (v->tl == l && v->tr == r) {
        v->sum = val * (v->tr - v->tl + 1);
        v->mod = val;
        return;
    }
    push(v);
    int tm = (v->tr + v->tl) / 2;
    up(v->l, l, min(r, tm), val);
    up(v->r, max(tm + 1, l), r, val);
    v->sum = v->l->sum + v->r->sum;
}

int get_sum(node *v, int l, int r){
    if (l > r) return 0;
    if (v->tl == l && v->tr == r) return v->sum;
    push(v);
    int tm = (v->tr + v->tl) / 2;
    int ans = 0;
    ans += get_sum(v->l, l, min(r, tm));
    ans += get_sum(v->r, max(l, tm + 1), r);
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
//    freopen("input.txt", "r", stdin);
    int m;
    cin >> m;
    int c = 0;
    while (m--){
        int tp,l,r;
        cin >> tp >> l >> r;
        if (tp == 1){
            cout << (c = get_sum(root, l + c, r + c))    << "\n";
//            up(root, l + c, r + c, 0);
        }else{
            up(root, l + c, r + c, 1);
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	20 ms	5100 KB	Output is correct
5	Correct	20 ms	6124 KB	Output is correct
6	Correct	19 ms	5868 KB	Output is correct
7	Correct	21 ms	6124 KB	Output is correct
8	Correct	161 ms	44652 KB	Output is correct
9	Correct	321 ms	77548 KB	Output is correct
10	Correct	334 ms	85484 KB	Output is correct
11	Correct	340 ms	91756 KB	Output is correct
12	Correct	338 ms	94572 KB	Output is correct
13	Correct	314 ms	110060 KB	Output is correct
14	Correct	342 ms	111212 KB	Output is correct
15	Correct	519 ms	201708 KB	Output is correct
16	Correct	522 ms	203444 KB	Output is correct
17	Correct	338 ms	115052 KB	Output is correct
18	Correct	325 ms	114884 KB	Output is correct
19	Correct	513 ms	207812 KB	Output is correct
20	Correct	513 ms	207724 KB	Output is correct