답안 #106561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106561 2019-04-19T04:42:38 Z Hideo 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
558 ms 159768 KB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pi pair < int, int >
#define pii pair < int, pi >
#define vii vector < pi >

const int N = 1e5 + 7;
const int INF = 1e9;

int n, c, x;

struct ST{
    int l, r, s, val;
    ST(){
        l = r = s = val = 0;
    }
};
ST t[100 * N];

void push (int v, int l, int r){
    if (l != r){
        if (!t[v].l)
            t[v].l = ++c;
        if (!t[v].r)
            t[v].r = ++c;
    }
    if (t[v].val){
        t[v].s = r - l + 1;
        t[t[v].l].val = t[t[v].r].val = 1;
    }
}

void upd (int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if (ql <= l && r <= qr){
        t[v].val = 1;
        push(v, l, r);
        return;
    }
    if (r < ql || l > qr)
        return;
    int mid = (l + r) >> 1;
    upd(t[v].l, l, mid, ql, qr);
    upd(t[v].r, mid + 1, r, ql, qr);
    t[v].s = t[t[v].l].s + t[t[v].r].s;
}

int get (int v, int l, int r, int ql, int qr){
    push(v, l, r);
    if (ql <= l && r <= qr)
        return t[v].s;
    if (r < ql || l > qr)
        return 0;
    int mid = (l + r) >> 1;
    return get(t[v].l, l, mid, ql, qr) + get(t[v].r, mid + 1, r, ql, qr);
}
main(){
    c = 1;
    cin >> n;
    for (int i = 1; i <= n; i++){
        int t, l, r;
        scanf("%d%d%d", &t, &l, &r);
        if (t == 1){
            x = get(1, 1, INF, l + x, r + x);
            printf("%d\n", x);
        }
        else
            upd(1, 1, INF, l + x, r + x);
    }
}

Compilation message

apple.cpp:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
apple.cpp: In function 'int main()':
apple.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 156920 KB Output is correct
2 Correct 139 ms 156984 KB Output is correct
3 Correct 126 ms 156892 KB Output is correct
4 Correct 135 ms 156920 KB Output is correct
5 Correct 164 ms 157008 KB Output is correct
6 Correct 148 ms 156920 KB Output is correct
7 Correct 137 ms 156920 KB Output is correct
8 Correct 282 ms 157048 KB Output is correct
9 Correct 457 ms 157432 KB Output is correct
10 Correct 467 ms 157560 KB Output is correct
11 Correct 444 ms 157444 KB Output is correct
12 Correct 489 ms 157504 KB Output is correct
13 Correct 425 ms 157584 KB Output is correct
14 Correct 416 ms 159480 KB Output is correct
15 Correct 551 ms 159768 KB Output is correct
16 Correct 544 ms 159736 KB Output is correct
17 Correct 415 ms 159532 KB Output is correct
18 Correct 480 ms 159608 KB Output is correct
19 Correct 518 ms 159608 KB Output is correct
20 Correct 558 ms 159736 KB Output is correct