oj.uz

답안 #519990

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
519990 2022-01-28T02:59:21 Z XII 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 402 ms 153404 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IZhO12_apple"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int M = 1e5 + 1;
struct node{
    int sum, lz, be, en, l, r;
    node(): sum(0), lz(0), l(-1), r(-1) {}
};
node ST[M * 64];
int cnt = 1;

void down(const int &id){
    int mi = (ST[id].be + ST[id].en) / 2;
    if(ST[id].l == -1){
        ST[id].l = ++cnt;
        ST[cnt].be = ST[id].be;
        ST[cnt].en = mi;
    }
    if(ST[id].r == -1){
        ST[id].r = ++cnt;
        ST[cnt].be = mi + 1;
        ST[cnt].en = ST[id].en;
    }
    if(ST[id].lz){
        ST[ST[id].l].lz = ST[ST[id].r].lz = ST[id].lz;
        ST[ST[id].l].sum = (mi - ST[id].be + 1);
        ST[ST[id].r].sum = (ST[id].en - mi);
        ST[id].lz = 0;
    }
}

void update(const int &l, const int &r, const int &v, int id = 1){
    if(l <= ST[id].be && ST[id].en <= r){
        ST[id].sum = (ST[id].en - ST[id].be + 1);
        ST[id].lz = 1;
        return;
    }
    int mi = (ST[id].be + ST[id].en) / 2;
    if(ST[id].l == -1){
        ST[id].l = ++cnt;
        ST[cnt].be = ST[id].be;
        ST[cnt].en = mi;
    }
    if(ST[id].r == -1){
        ST[id].r = ++cnt;
        ST[cnt].be = mi + 1;
        ST[cnt].en = ST[id].en;
    }
    down(id);
    if(l <= mi) update(l, r, v, ST[id].l);
    if(mi < r) update(l, r, v, ST[id]. r);
    ST[id].sum = ST[ST[id].l].sum + ST[ST[id].r].sum;
}

int query(const int &l, const int &r, int id = 1){
    if(l <= ST[id].be && ST[id].en <= r) return ST[id].sum;
    int mi = (ST[id].be + ST[id].en) / 2;
    down(id);
    int ret = 0;
    if(l <= mi) ret += query(l, r, ST[id].l);
    if(mi < r) ret += query(l, r, ST[id].r);
    return ret;
}

int C;

int main(){
    IOS;
    Fi();
    int m; cin >> m;
    ST[1].be = 1, ST[1].en = 1e9;
    while(m--){
        int t, x, y; cin >> t >> x >> y;
        if(t == 2) update(x + C, y + C, 1);
        else cout << (C = query(x + C, y + C)) << "\n";
    }
    return 0;
}

Compilation message

apple.cpp: In function 'void Fi()':
apple.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 150552 KB Output is correct
2 Correct 59 ms 150596 KB Output is correct
3 Correct 59 ms 150596 KB Output is correct
4 Correct 72 ms 150708 KB Output is correct
5 Correct 84 ms 150764 KB Output is correct
6 Correct 75 ms 150708 KB Output is correct
7 Correct 81 ms 150784 KB Output is correct
8 Correct 190 ms 151624 KB Output is correct
9 Correct 304 ms 152716 KB Output is correct
10 Correct 309 ms 152644 KB Output is correct
11 Correct 321 ms 152712 KB Output is correct
12 Correct 318 ms 152708 KB Output is correct
13 Correct 302 ms 153264 KB Output is correct
14 Correct 295 ms 153064 KB Output is correct
15 Correct 402 ms 153148 KB Output is correct
16 Correct 387 ms 153356 KB Output is correct
17 Correct 313 ms 153308 KB Output is correct
18 Correct 294 ms 153144 KB Output is correct
19 Correct 399 ms 153404 KB Output is correct
20 Correct 391 ms 153248 KB Output is correct