Submission #930579

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930579	2024-02-20T07:09:31 Z	dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	321 ms	262144 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() {
        //cout << l sp r sp v sp lazy << '\n';
        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() {
        //cout << l sp r sp v sp lazy << '\n';
        if (lazy) push();
        if (l >= L && r <= R) {
            //cout << "PUSHING: " << l sp r << '\n';
            lazy=1;
            push();
            return;
        } 
        int m = (l+r) >> 1;
        if (R >= m+1) {
            if (!c[1]) c[1] =  new DST(m+1,r);
            c[1]->update();
        }
        if (L <= m) {
            if (!c[0]) c[0] = new DST(l,m);
            c[0]->update();
        }
        v = 0;
        if (c[0]) {
            if (c[0]->lazy) c[0]->push();
            v+=c[0]->v;
        }
        if (c[1]) {
            if (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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	13 ms	10332 KB	Output is correct
5	Correct	16 ms	12380 KB	Output is correct
6	Correct	16 ms	12184 KB	Output is correct
7	Correct	16 ms	12536 KB	Output is correct
8	Correct	152 ms	93260 KB	Output is correct
9	Correct	284 ms	159640 KB	Output is correct
10	Correct	317 ms	178432 KB	Output is correct
11	Correct	319 ms	192848 KB	Output is correct
12	Correct	321 ms	199276 KB	Output is correct
13	Correct	288 ms	243420 KB	Output is correct
14	Correct	294 ms	246448 KB	Output is correct
15	Runtime error	282 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-