oj.uz

답안 #387974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387974 2021-04-09T15:38:29 Z Aryan_Raina 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
 443 ms 81292 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define ar array

const int INF = 1e15;
const int MOD = 1e9+7;

template<class T> struct SparseSegTree {
    int size, CNT = 1;
    vector<T> values, operations, lc, rc;
    const T NO_OPERATION = 0;
    const T NEUTRAL_ELEMENT = 0;
    
    SparseSegTree(int n, int max_nodes) {
        size = 1;
        while (size < n) size <<= 1;
        values.assign(max_nodes, 0);
        operations.assign(max_nodes, NO_OPERATION);
        lc.assign(max_nodes, -1); rc.assign(max_nodes, -1);
    }

    void modify_op(T &a, T b, int len) {
        if (b == NO_OPERATION) return;
        a = b*len;
    }

    T calc_op(T a, T b) {
        return a + b;
    }

    void propogate(int x, int lx, int rx) {
        if (rx - lx == 1) return;
        int m = (lx + rx) >> 1;
        if (lc[x] == -1) lc[x] = CNT++;
        if (rc[x] == -1) rc[x] = CNT++;
        modify_op(operations[lc[x]], operations[x], 1);
        modify_op(operations[rc[x]], operations[x], 1);
        modify_op(values[lc[x]], operations[x], m - lx);
        modify_op(values[rc[x]], operations[x], rx - m);
        operations[x] = NO_OPERATION;
    }
 
    void modify(int l, int r, T v, int x, int lx, int rx) {
        if (lx >= r || l >= rx) return;
        if (l <= lx && rx <= r) {
            modify_op(operations[x], v, 1);
            modify_op(values[x], v, rx - lx);
            return;
        }
        propogate(x, lx, rx);
        int m = (lx + rx) >> 1;
        modify(l, r, v, lc[x], lx, m);
        modify(l, r, v, rc[x], m, rx);
        values[x] = calc_op(values[lc[x]], values[rc[x]]);
    }
    void modify(int l, int r, T v) { modify(l, r, v, 0, 0, size); }

    T calc(int l, int r, int x, int lx, int rx) {
        if (lx >= r || l >= rx) return NEUTRAL_ELEMENT;
        if (l <= lx && rx <= r) return values[x];
        propogate(x, lx, rx);
        int m = (lx + rx) >> 1;
        return calc_op(calc(l, r, lc[x], lx, m), 
            calc(l, r, rc[x], m, rx));
    }
    T calc(int l, int r) { return calc(l, r, 0, 0, size); }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int q; cin>>q;
    int c = 0;
    int MXN = 1e9+9, MX_NODES = 5e6;
    SparseSegTree<int> st(MXN, MX_NODES);
    while (q--) {
        int t, l, r; cin>>t>>l>>r;
        l += c, r += c;
        assert(l-1 >= 0);
        assert(r <= 1e9+9);
        if (t == 1) {
            c = st.calc(l-1, r);
            cout<<c<<"\n";
        } else if (t == 2) {
            st.modify(l-1, r, 1);
        }
    }
}

Compilation message

apple.cpp:8:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
    8 | const int INF = 1e15;
      |                 ^~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 78576 KB Output is correct
2 Correct 40 ms 78560 KB Output is correct
3 Correct 41 ms 78556 KB Output is correct
4 Correct 53 ms 78592 KB Output is correct
5 Correct 55 ms 78648 KB Output is correct
6 Correct 57 ms 78548 KB Output is correct
7 Correct 55 ms 78548 KB Output is correct
8 Correct 160 ms 78688 KB Output is correct
9 Correct 325 ms 78864 KB Output is correct
10 Correct 310 ms 78964 KB Output is correct
11 Correct 315 ms 78864 KB Output is correct
12 Correct 331 ms 79036 KB Output is correct
13 Correct 302 ms 79044 KB Output is correct
14 Correct 267 ms 79088 KB Output is correct
15 Correct 388 ms 79688 KB Output is correct
16 Correct 443 ms 81292 KB Output is correct
17 Correct 272 ms 81092 KB Output is correct
18 Correct 279 ms 81096 KB Output is correct
19 Correct 387 ms 81228 KB Output is correct
20 Correct 394 ms 81204 KB Output is correct