답안 #387961

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
387961	2021-04-09T15:13:19 Z	Aryan_Raina	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	566 ms	262144 KB

apple

#include <bits/stdc++.h>
using namespace std;

#define int 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) {
        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;
        if (t == 1) {
            c = st.calc(l-1, r);
            cout<<c<<"\n";
        } else if (t == 2) {
            st.modify(l-1, r, 1);
        }
    }
}  

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	70 ms	156740 KB	Output is correct
2	Correct	72 ms	156820 KB	Output is correct
3	Correct	72 ms	156860 KB	Output is correct
4	Correct	97 ms	156968 KB	Output is correct
5	Correct	95 ms	157032 KB	Output is correct
6	Correct	94 ms	156976 KB	Output is correct
7	Correct	92 ms	157048 KB	Output is correct
8	Correct	266 ms	157252 KB	Output is correct
9	Correct	522 ms	157400 KB	Output is correct
10	Correct	527 ms	157584 KB	Output is correct
11	Correct	522 ms	157252 KB	Output is correct
12	Correct	534 ms	157244 KB	Output is correct
13	Correct	442 ms	157356 KB	Output is correct
14	Correct	433 ms	157252 KB	Output is correct
15	Runtime error	566 ms	262144 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-