oj.uz

답안 #387969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387969 2021-04-09T15:26:08 Z Aryan_Raina 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
 479 ms 161104 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++;
        assert(CNT < 5e6);
        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) {
        propogate(x, lx, 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;
        }
        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) {
        propogate(x, lx, rx);
        if (lx >= r || l >= rx) return NEUTRAL_ELEMENT;
        if (l <= lx && rx <= r) return values[x];
        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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 78540 KB Output is correct
2 Correct 41 ms 78564 KB Output is correct
3 Correct 41 ms 78600 KB Output is correct
4 Correct 59 ms 78528 KB Output is correct
5 Correct 61 ms 78532 KB Output is correct
6 Correct 63 ms 78692 KB Output is correct
7 Correct 63 ms 78564 KB Output is correct
8 Correct 216 ms 78764 KB Output is correct
9 Correct 479 ms 78972 KB Output is correct
10 Correct 444 ms 78976 KB Output is correct
11 Correct 463 ms 78936 KB Output is correct
12 Correct 463 ms 78960 KB Output is correct
13 Correct 385 ms 79120 KB Output is correct
14 Correct 405 ms 79056 KB Output is correct
15 Runtime error 408 ms 161104 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -