Submission #930580

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
930580	2024-02-20T07:10:24 Z	dosts	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	371 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	12 ms	7760 KB	Output is correct
5	Correct	15 ms	9304 KB	Output is correct
6	Correct	14 ms	9052 KB	Output is correct
7	Correct	16 ms	9308 KB	Output is correct
8	Correct	135 ms	69864 KB	Output is correct
9	Correct	257 ms	118532 KB	Output is correct
10	Correct	272 ms	132568 KB	Output is correct
11	Correct	286 ms	143452 KB	Output is correct
12	Correct	297 ms	148424 KB	Output is correct
13	Correct	263 ms	181416 KB	Output is correct
14	Correct	260 ms	183540 KB	Output is correct
15	Runtime error	371 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-