Submission #387974

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
387974	2021-04-09T15:38:29 Z	Aryan_Raina	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	443 ms	81292 KB

apple

#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

#	Verdict	Execution time	Memory	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