oj.uz

답안 #986180

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
986180 2024-05-20T03:30:59 Z hanifchdn 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
 340 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define uint unsigned int
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int N = 2e5 + 5;

struct node {
    ll sum, lazy;
    node *l, *r;
    node() : sum(0), lazy(0), l(nullptr), r(nullptr) {}
};
 
node *root = new node();
 
void push(node *x, int tl, int tr) {
    if (x->lazy == 0) return;
    x->sum = tr - tl + 1;
    if (tl == tr) {
        x->lazy = 0;
        return;
    }
    if (x->l == nullptr) {
        x->l = new node();
        x->r = new node();
    }
    x->l->lazy = x->lazy;
    x->r->lazy = x->lazy;
    x->lazy = 0;
}

void update(node *x, int tl, int tr, int l, int r) {
    push(x, tl, tr);
    if (tr < l or r < tl) return;
    if (l <= tl and tr <= r) {
        x->lazy = 1;
        push(x, tl, tr);
        return;
    }
    if (x->l == nullptr) {
        x->l = new node();
        x->r = new node();
    }
    int tm = (tl + tr) / 2;
    update(x->l, tl, tm, l, r);
    update(x->r, tm + 1, tr, l, r);
    x->sum = x->l->sum + x->r->sum;
}
 
ll get(node *x, int tl, int tr, int l, int r) {
    if (tr < l or r < tl) return 0;
    push(x, tl, tr);
    int tm = (tl + tr) / 2;
    if (l <= tl and tr <= r) return x->sum;
    if (x->l == nullptr) {
        x->l = new node();
        x->r = new node();
    }
    return get(x->l, tl, tm, l, r) + get(x->r, tm + 1, tr, l, r);
}

int main() { 
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q;
    cin >> q;
    int c = 0;
    while (q--) {
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1) {
            c = get(root, 1, 1e9, x + c, y + c);
            cout << c << "\n";
        }
        else {
            update(root, 1, 1e9, x + c, y + c);
        }
    }   
}

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 12 ms 7772 KB Output is correct
5 Correct 15 ms 9304 KB Output is correct
6 Correct 15 ms 9124 KB Output is correct
7 Correct 15 ms 9308 KB Output is correct
8 Correct 126 ms 69316 KB Output is correct
9 Correct 260 ms 118612 KB Output is correct
10 Correct 268 ms 132688 KB Output is correct
11 Correct 276 ms 143696 KB Output is correct
12 Correct 287 ms 148820 KB Output is correct
13 Correct 262 ms 181332 KB Output is correct
14 Correct 276 ms 183648 KB Output is correct
15 Runtime error 340 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -