oj.uz

Submission #387802

# Submission time Handle Problem Language Result Execution time Memory
387802 2021-04-09T08:42:37 Z Aryan_Raina Monkey and Apple-trees (IZhO12_apple) C++14
0 / 100
 719 ms 262148 KB 
#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 Node {
    Node *lc = 0, *rc = 0;
    int lx, rx; T value, operation;

    const T NEUTRAL_ELEMENT = 0;
    const T NO_OPERATION = 0;

    T calc_op(T a, T b) {
        return a + b;
    }

    void modify_op(T &a, T b, int len) {
        if (b == NO_OPERATION) return;
        a = b*len;
    }

    Node(int _lx, int _rx) : lx(_lx), rx(_rx) {
        value = NEUTRAL_ELEMENT;
        operation = NO_OPERATION;
    }
    Node(vector<T> &v, int _lx, int _rx) : lx(_lx), rx(_rx) {
        operation = NO_OPERATION;
        if (rx - lx == 1) value = v[lx];
        else {
            int m = (lx + rx) >> 1;
            lc = new Node(v, lx, m), rc = new Node(v, m, rx);
            value = calc_op(lc->value, rc->value);
        }
    }  

    void propogate() {
        if (rx - lx == 1) return;
        int m = (lx + rx) >> 1;
        if (!lc) lc = new Node(lx, m);
        if (!rc) rc = new Node(m, rx);
        modify_op(lc->operation, operation, 1);
        modify_op(rc->operation, operation, 1);
        modify_op(lc->value, operation, m-lx);
        modify_op(rc->value, operation, rx-m);
        operation = NO_OPERATION;
    }

    void set(int i, int v) {
        propogate();
        if (rx - lx == 1) return void(value = v);
        int m = (lx + rx) >> 1;
        if (i < m) lc->set(i, v);
        else rc->set(i, v);
        value = calc_op(lc->value, rc->value);
    }

    void modify(int l, int r, int v) {
        propogate();
        if (l >= rx || lx >= r) return;
        if (l <= lx && rx <= r) {
            modify_op(operation, v, 1);
            modify_op(value, v, rx - lx);
            return;
        }
        lc->modify(l, r, v); rc->modify(l, r, v);
        value = calc_op(lc->value, rc->value);
    }

    T calc(int l, int r) {
        propogate();
        if (l >= rx || lx >= r) return NEUTRAL_ELEMENT;
        if (l <= lx && rx <= r) return value;
        int x = calc_op(lc->calc(l, r), rc->calc(l, r));
        return x;
    }

};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int q; cin>>q;
    Node<int> smh(0, 1e9+7);
    int c = 0;
    while (q--) {
        //cout<<q<<endl;
        int t, l, r; cin>>t>>l>>r;
        l += c, r += c;
        if (t == 1) {
            c = smh.calc(l-1, r);
            cout<<c<<"\n";
        } else if (t == 2) {
            smh.modify(l-1, r, 1);
        }
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 32 ms 14224 KB Output is correct
5 Correct 32 ms 17132 KB Output is correct
6 Correct 38 ms 16548 KB Output is correct
7 Correct 35 ms 17152 KB Output is correct
8 Correct 372 ms 128748 KB Output is correct
9 Correct 667 ms 219312 KB Output is correct
10 Correct 676 ms 245844 KB Output is correct
11 Runtime error 719 ms 262148 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -