oj.uz

답안 #467699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467699 2021-08-24T06:00:00 Z jli12345 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 348 ms 103352 KB 
#include <bits/stdc++.h>
using namespace std;

void fastIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
}

struct Node{
    int lson, rson;
    int sum;
    int settag;
    Node(){
        lson = rson = -1;
        sum = 1;
        settag = -1;
    }
} st[64*100100];

int nodecnt = 1;

void pushdown(int node, int l, int mid, int r){
    if (st[node].lson == -1)
        st[node].lson = ++nodecnt;
    if (st[node].rson == -1)
        st[node].rson = ++nodecnt;
    if (st[node].settag == -1)
        return;
    st[st[node].lson].sum = (mid-l+1)*st[node].settag;
    st[st[node].rson].sum = (r-mid)*st[node].settag;
    st[st[node].lson].settag = st[st[node].rson].settag = st[node].settag;
    st[node].settag = -1;
}

void U(int node, int l, int r, int tl, int tr, int val){
    if (l > tr || r < tl)
        return;
    if (l >= tl && r <= tr){
        st[node].sum = (r-l+1)*val;
        st[node].settag = val;
        return;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    U(st[node].lson, l, mid, tl, tr, val);
    U(st[node].rson, mid+1, r, tl, tr, val);
    st[node].sum = st[st[node].lson].sum+st[st[node].rson].sum;
}

int S(int node, int l, int r, int tl, int tr){
    if (l > tr || r < tl)
        return 0;
    if (l >= tl && r <= tr){
        return st[node].sum;
    }
    int mid = (l+r)/2;
    pushdown(node, l, mid, r);
    return S(st[node].lson, l, mid, tl, tr)+S(st[node].rson, mid+1, r, tl, tr);
}

int main(){
    fastIO();
    int Q; cin >> Q;
    int C = 0;
    U(1, 1, 1000000000, 1, 1000000000, 0);
    while (Q--){
        int k; cin >> k;
        int a, b; cin >> a >> b;
        if (k == 1){
            int val = S(1, 1, 1000000000, a+C, b+C);
            cout << val << "\n";
            C = val;
        } else {
            U(1, 1, 1000000000, a+C, b+C, 1);
        }
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 100548 KB Output is correct
2 Correct 53 ms 100512 KB Output is correct
3 Correct 58 ms 100504 KB Output is correct
4 Correct 62 ms 100696 KB Output is correct
5 Correct 65 ms 100744 KB Output is correct
6 Correct 71 ms 100684 KB Output is correct
7 Correct 67 ms 100668 KB Output is correct
8 Correct 136 ms 101592 KB Output is correct
9 Correct 252 ms 102604 KB Output is correct
10 Correct 255 ms 102688 KB Output is correct
11 Correct 226 ms 102724 KB Output is correct
12 Correct 258 ms 102880 KB Output is correct
13 Correct 248 ms 103140 KB Output is correct
14 Correct 217 ms 103200 KB Output is correct
15 Correct 276 ms 103156 KB Output is correct
16 Correct 303 ms 103352 KB Output is correct
17 Correct 225 ms 103160 KB Output is correct
18 Correct 241 ms 103056 KB Output is correct
19 Correct 283 ms 103304 KB Output is correct
20 Correct 348 ms 103208 KB Output is correct