Submission #1125170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125170		Duine	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	431 ms	205628 KiB

apple

#include <bits/stdc++.h>

using namespace std;

int q; long long c = 0;
struct TYPE {
    TYPE *le = NULL, *ri = NULL; 
    int from, to, val = 0, lz = 0;
    
    void expand ()
    {
        if (le != NULL) return;
        le = new TYPE ();
        ri = new TYPE ();
        
        int mid = from + ((to-from) >> 1);
        le->from = from;
        le->to = mid;
        ri->from = mid+1;
        ri->to = to;
    }
};

void push (TYPE *sm, TYPE *le, TYPE *ri, int l, int r, int mid)
{
    le->val = mid-l+1;
    ri->val = r-mid;
    le->lz = ri->lz = 1;
    
    sm->lz = 0;
}

void update (TYPE *sm, int u, int v)
{
    int l = sm->from, r = sm->to;
    
    if (u > r || v < l) return;
    if (u <= l && r <= v) {
        sm->val = r-l+1;
        sm->lz = 1;
        return;
    }
    
    sm->expand();
    int mid = l + ((r-l) >> 1);
    if (sm->lz != 0) push (sm, sm->le, sm->ri, l, r, mid);
    
    update (sm->le, u, v);
    update (sm->ri, u, v);
    
    sm->val = sm->le->val + sm->ri->val;
}

int get (TYPE *sm, int u, int v)
{
    int l = sm->from, r = sm->to;
    if (u > r || v < l) return 0;
    if (u <= l && r <= v) return sm->val;
    
    sm->expand();
    int mid = l + ((r-l) >> 1);
    if (sm->lz != 0) push (sm, sm->le, sm->ri, l, r, mid);
    
    return get (sm->le, u, v) + get (sm->ri, u, v);
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    TYPE *node;
    node = new TYPE ();
    node->from = 1; node->to = 1e9+7;
    
    cin >> q;
    int choice; long long l, r;
    while (q--){
        cin >> choice >> l >> r;
        l += c; r += c;
        
        if (choice == 1) 
        {
            int tmp = get (node, l, r);
            c = tmp;
            cout << tmp << '\n';
        }
        else update (node, l, r);
    }
    
    return 0;
}

• Subtask 1: 100 / 100