Submission #1057507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057507		Mihailo	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	293 ms	207700 KiB

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 / 100