답안 #930579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930579 2024-02-20T07:09:31 Z dosts 원숭이와 사과 나무 (IZhO12_apple) C++17
0 / 100
321 ms 262144 KB
#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();
}
# 결과 실행 시간 메모리 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 -