oj.uz

답안 #501959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
501959 2022-01-04T23:39:52 Z BeanZ 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 425 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const int N = 1e7 + 5;
const long long mod = 1e9 + 7;
const int mod2 = 998244353;
const long long lim = 1e9;
const int lg = 22;
const int base = 311;
const int base2 = 511;
const long double eps = 1e-12;
ll st[N], lazy[N], L[N], R[N];
ll cnt = 1;
void down(ll k, ll l, ll r){
    if (L[k] == 0) cnt++, L[k] = cnt;
    if (R[k] == 0) cnt++, R[k] = cnt;
    ll mid = (l + r) >> 1;
    st[L[k]] = mid - l + 1;
    st[R[k]] = r - mid;
    lazy[L[k]] = 1;
    lazy[R[k]] = 1;
    lazy[k] = 0;
}
ll get(ll k, ll l, ll r, ll x, ll y){
    if (l != r && lazy[k]) down(k, l, r);
    if (x > r || y < l) return 0;
    if (x <= l && y >= r) return st[k];
    ll res = 0;
    ll mid = (l + r) >> 1;
    if (L[k]) res = res + get(L[k], l, mid, x, y);
    if (R[k]) res = res + get(R[k], mid + 1, r, x, y);
    //cout << l << " " << r << " " << res << endl;
    return res;
}
void upd(ll k, ll l, ll r, ll x, ll y){
    if (l != r && lazy[k]) down(k, l, r);
    if (x > r || y < l) return;
    if (x <= l && y >= r){
        st[k] = r - l + 1;
        lazy[k] = 1;
        return;
    }
    ll mid = (l + r) >> 1;
    if (L[k] == 0) cnt++, L[k] = cnt;
    if (R[k] == 0) cnt++, R[k] = cnt;
    upd(L[k], l, mid, x, y);
    upd(R[k], mid + 1, r, x, y);
    st[k] = st[L[k]] + st[R[k]];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("tests.inp", "r")){
        freopen("tests.inp", "r", stdin);
        freopen("tests.out", "w", stdout);
    }
    ll m;
    cin >> m;
    ll c = 0;
    while (m--){
        ll d, x, y;
        cin >> d >> x >> y;
        x += c;
        y += c;
        if (d == 1){
            c = get(1, 1, lim, x, y);
            cout << c << endl;
        } else {
            upd(1, 1, lim, x, y);
        }
    }
}
/*
Ans:

Out:
*/

Compilation message

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

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 11 ms 5796 KB Output is correct
5 Correct 16 ms 7024 KB Output is correct
6 Correct 16 ms 6732 KB Output is correct
7 Correct 14 ms 7000 KB Output is correct
8 Correct 136 ms 51412 KB Output is correct
9 Correct 301 ms 87424 KB Output is correct
10 Correct 274 ms 98096 KB Output is correct
11 Correct 304 ms 108244 KB Output is correct
12 Correct 297 ms 111928 KB Output is correct
13 Correct 246 ms 138948 KB Output is correct
14 Correct 254 ms 140340 KB Output is correct
15 Correct 407 ms 254592 KB Output is correct
16 Correct 415 ms 256560 KB Output is correct
17 Correct 268 ms 145488 KB Output is correct
18 Correct 263 ms 145460 KB Output is correct
19 Correct 411 ms 262144 KB Output is correct
20 Correct 425 ms 262144 KB Output is correct