Submission #930581

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930581	2024-02-20T07:12:49 Z	dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	236 ms	166956 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	7 ms	4188 KB	Output is correct
5	Correct	9 ms	4952 KB	Output is correct
6	Correct	8 ms	4896 KB	Output is correct
7	Correct	9 ms	4952 KB	Output is correct
8	Correct	63 ms	37676 KB	Output is correct
9	Correct	124 ms	65360 KB	Output is correct
10	Correct	135 ms	71760 KB	Output is correct
11	Correct	138 ms	76628 KB	Output is correct
12	Correct	134 ms	78672 KB	Output is correct
13	Correct	136 ms	86816 KB	Output is correct
14	Correct	125 ms	86604 KB	Output is correct
15	Correct	207 ms	161608 KB	Output is correct
16	Correct	218 ms	163068 KB	Output is correct
17	Correct	129 ms	91400 KB	Output is correct
18	Correct	125 ms	91476 KB	Output is correct
19	Correct	214 ms	166892 KB	Output is correct
20	Correct	236 ms	166956 KB	Output is correct