Submission #387966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
387966	2021-04-09T15:23:00 Z	Aryan_Raina	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	548 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++;
        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);
        }
    }
}  

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	156740 KB	Output is correct
2	Correct	69 ms	156812 KB	Output is correct
3	Correct	69 ms	156788 KB	Output is correct
4	Correct	105 ms	156868 KB	Output is correct
5	Correct	92 ms	156892 KB	Output is correct
6	Correct	118 ms	156792 KB	Output is correct
7	Correct	93 ms	156856 KB	Output is correct
8	Correct	278 ms	157028 KB	Output is correct
9	Correct	541 ms	157256 KB	Output is correct
10	Correct	538 ms	157344 KB	Output is correct
11	Correct	539 ms	157300 KB	Output is correct
12	Correct	545 ms	157220 KB	Output is correct
13	Correct	461 ms	157264 KB	Output is correct
14	Correct	453 ms	157332 KB	Output is correct
15	Runtime error	548 ms	262144 KB	Execution killed with signal 6
16	Halted	0 ms	0 KB	-