Submission #930581

#	Time	Username	Problem	Language	Result	Execution time	Memory
930581		dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	236 ms	166956 KiB

apple

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
//#define int long long
#define ff first
#define ss second
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
template<typename T1, typename T2> bool MIN(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<typename T1, typename T2> bool MAX(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 2e5+1;
int L,R;
struct DST {
    int l,r,v=0,lazy=0;
    DST* c[2];
    DST(int lll,int rrr): l(lll),r(rrr),c{NULL,NULL}{};

    void push() {
        v = r-l+1;
        if (l != r) {
            int m = (l+r) >> 1;
            if (!c[0]) c[0] = new DST(l,m);
            if (!c[1]) c[1] = new DST(m+1,r);
            c[0]->lazy = 1;
            c[1]->lazy = 1;
        }
        lazy = 0;
    }

    int query() {
        if (lazy) push();
        if (l >= L && r <= R) return v;
        int m =  (l+r) >> 1,ans = 0;
        if (R >= m+1 && c[1]) ans+=c[1]->query();
        if (L <= m && c[0]) ans+=c[0]->query();
        return ans;
    }

    void update() {
        if (lazy) push();
        if (l >= L && r <= R) {
            lazy=1;
            push();
            return;
        } 
        int m = (l+r) >> 1;
        if (R >= m+1) {
            if (!c[1]) c[1] =  new DST(m+1,r);
            if (!c[1]->lazy && c[1]->v != r-m)c[1]->update();
        }
        if (L <= m) {
            if (!c[0]) c[0] = new DST(l,m);
            if (!c[0]->lazy && c[0]->v != m-l+1)c[0]->update();
        }
        v = 0;
        if (c[0]) {
            if (c[0]->v != m-l+1 && c[0]->lazy) c[0]->push();
            v+=c[0]->v;
        }
        if (c[1]) {
            if (c[1]->v != r-m && c[1]->lazy) c[1]->push();
            v+=c[1]->v;
        }
    }
};

void solve() {  
    DST DoST(1,1e9);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l,r;
            cin >> l >> r;
            l+=c;
            r+=c;
            L = l;
            R = r;
            c = DoST.query();
            cout << c << '\n';
        }
        else {
            int l,r;
            cin >> l >> r;
            l+=c;
            r+=c;
            L = l;
            R = r;
            DoST.update();
        }
    }
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif

    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

• Subtask 1: 100 / 100