oj.uz

답안 #1089497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1089497 2024-09-16T15:29:00 Z BLOBVISGOD 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 241 ms 106324 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
#define all(x) x.begin(),x.end()
#define sz(x) int(x.size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const int N = 1e5+10;

struct node{
    int sm, lazy, l, r, lc, rc;
    int val(){
        return lazy?(r-l):sm;
    }
};

int n = 1;
node seg[81*N];

void ensure(int id){
    auto& v = seg[id];
    int mid = (v.l+v.r)/2;
    if (v.lc<0){
        seg[n] = {0,v.lazy,v.l,mid,-1,-1};
        v.lc = n++;
    }if (v.rc<0){
        seg[n] = {0,v.lazy,mid,v.r,-1,-1};
        v.rc = n++;
    }
}

void push(int id){
    ensure(id);
    auto& v = seg[id];
    if (v.lazy) seg[v.lc].lazy = v.lazy, seg[v.rc].lazy = v.lazy;
    v.sm = v.val();
    v.lazy = 0;
}

void pull(int id){
    auto& v = seg[id];
    v.sm = seg[v.lc].val() + seg[v.rc].val();
}

void ud(int i, int ql, int qr){
    auto& v = seg[i];
    if (v.l >= qr or v.r <= ql) return;
    if (v.l >= ql and v.r <= qr){
        seg[i].lazy = 1;
        return;
    }
    push(i);
    ud(v.lc,ql,qr), ud(v.rc,ql,qr);
    pull(i);
}

void update(int l, int r) {
    ud(0,l,r);
}

int gt(int i, int ql, int qr){
    auto& v = seg[i];
    if (v.l >= qr or v.r <= ql) return 0;
    if (v.l >= ql and v.r <= qr) 
        return v.val();
    push(i);
    return gt(v.lc,ql,qr) + gt(v.rc,ql,qr);
}

int get(int l, int r){
    return gt(0,l,r);
}


int main(){
    seg[0] = {0,0,0,1<<30,-1,-1};

    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int m, last = 0; cin >> m;

    while(m--){
        int t,x,y; cin >> t >> x >> y;
        x += last, y += last;
        if (t==1){
            last = get(x,y+1);
            cout << last << '\n';
        }else{
            update(x,y+1);
        }
    }

}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 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 9 ms 2704 KB Output is correct
5 Correct 11 ms 3220 KB Output is correct
6 Correct 12 ms 3164 KB Output is correct
7 Correct 11 ms 3420 KB Output is correct
8 Correct 70 ms 23376 KB Output is correct
9 Correct 150 ms 39636 KB Output is correct
10 Correct 158 ms 44624 KB Output is correct
11 Correct 165 ms 47700 KB Output is correct
12 Correct 154 ms 49188 KB Output is correct
13 Correct 149 ms 56956 KB Output is correct
14 Correct 145 ms 57428 KB Output is correct
15 Correct 206 ms 103292 KB Output is correct
16 Correct 201 ms 104152 KB Output is correct
17 Correct 147 ms 59220 KB Output is correct
18 Correct 150 ms 59284 KB Output is correct
19 Correct 216 ms 106320 KB Output is correct
20 Correct 241 ms 106324 KB Output is correct