Submission #387974

#	Time	Username	Problem	Language	Result	Execution time	Memory
387974		Aryan_Raina	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	443 ms	81292 KiB

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 (stderr)

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 / 100