oj.uz

답안 #387829

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
387829 2021-04-09T09:02:31 Z Aryan_Raina 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
 528 ms 262148 KB 
#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 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);
        }
    }
}

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
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 22 ms 8612 KB Output is correct
5 Correct 26 ms 10360 KB Output is correct
6 Correct 26 ms 9968 KB Output is correct
7 Correct 27 ms 10320 KB Output is correct
8 Correct 233 ms 76916 KB Output is correct
9 Correct 483 ms 130736 KB Output is correct
10 Correct 494 ms 146884 KB Output is correct
11 Correct 524 ms 161356 KB Output is correct
12 Correct 527 ms 166576 KB Output is correct
13 Correct 472 ms 207140 KB Output is correct
14 Correct 472 ms 209172 KB Output is correct
15 Runtime error 528 ms 262148 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -