Submission #1057507

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1057507	2024-08-13T20:48:01 Z	Mihailo	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	293 ms	207700 KB

apple

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
#define pll pair<long long, long long>
#define MOD 1000000007
typedef long long ll;
using namespace std;
mt19937 mt(time(nullptr));

struct node {
    ll l, r, red;
    node *left, *right;
    node(ll l, ll r, ll clr): l(l), r(r), red(clr*(r-l+1)), left(nullptr), right(nullptr) {};
};

node *tree=nullptr;
ll m, d, x, y;

void prop(node *cur) {
    if(cur->l!=cur->r&&cur->left==nullptr) {
        ll m=(cur->l+cur->r)/2;
        if(cur->red) {
            cur->left=new node(cur->l, m, 1);
            cur->right=new node(m+1, cur->r, 1);
        }
        else {
            cur->left=new node(cur->l, m, 0);
            cur->right=new node(m+1, cur->r, 0);
        }
    }
    if(cur->l!=cur->r&&cur->red==(cur->r-cur->l+1)) {
        cur->left->red=cur->left->r-cur->left->l+1;
        cur->right->red=cur->right->r-cur->right->l+1;
    }
}

void update(node *cur, ll l, ll r) {
    if(l>r) return;
    if(cur->l==l&&cur->r==r) {
        cur->red=r-l+1;
        return;
    }
    prop(cur);
    update(cur->left, l, min(r, cur->left->r));
    update(cur->right, max(l, cur->right->l), r);
    cur->red=cur->left->red+cur->right->red;
}

ll query(node *cur, ll l, ll r) {
    if(l>r) return 0;
    if(cur->l==l&&cur->r==r) {
        return cur->red;
    }
    prop(cur);
    return query(cur->left, l, min(r, cur->left->r))+query(cur->right, max(l, cur->right->l), r);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    tree=new node(1, 1e9, 0);
    cin>>m;
    ll c=0;
    while(m--) {
        cin>>d>>x>>y;
        x+=c;
        y+=c;
        if(d==2) {
            update(tree, x, y);
        }
        else {
            c=query(tree, x, y);
            cout<<c<<'\n';
        }
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	600 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	8 ms	4956 KB	Output is correct
5	Correct	9 ms	6104 KB	Output is correct
6	Correct	9 ms	5980 KB	Output is correct
7	Correct	9 ms	5976 KB	Output is correct
8	Correct	79 ms	44632 KB	Output is correct
9	Correct	172 ms	77340 KB	Output is correct
10	Correct	187 ms	85376 KB	Output is correct
11	Correct	172 ms	91732 KB	Output is correct
12	Correct	196 ms	94560 KB	Output is correct
13	Correct	154 ms	110160 KB	Output is correct
14	Correct	231 ms	111188 KB	Output is correct
15	Correct	293 ms	201808 KB	Output is correct
16	Correct	249 ms	203204 KB	Output is correct
17	Correct	152 ms	114824 KB	Output is correct
18	Correct	151 ms	115024 KB	Output is correct
19	Correct	255 ms	207700 KB	Output is correct
20	Correct	275 ms	207696 KB	Output is correct