답안 #550669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
550669	2022-04-18T19:29:31 Z	Vladth11	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	121 ms	262144 KB

apple

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;

const ll NMAX = 100001;
const ll VMAX = 10000001;
const ll INF = (1LL << 55);
const ll MOD = 1000007;
const ll BLOCK = 1000000;
const ll base = 1000000001;
const ll nr_of_bits = 18;

struct node {
    int l, r;
    int sum;
    int lazy;
    void init() {
        l = r = -1;
        lazy = sum = 0;
    }
} aint[NMAX * 70];

int nodes;

void propaga(int node, int st, int dr) {
    if(aint[node].lazy == 0)
        return;
    if(st != dr) {
        if(aint[node].l == -1) {
            aint[node].l = ++nodes;
            aint[nodes].init();
        }
        if(aint[node].r == -1) {
            aint[node].r = ++nodes;
            aint[nodes].init();
        }
        aint[aint[node].l].lazy = aint[aint[node].r].lazy = 1;
    }
    aint[node].lazy = 0;
    aint[node].sum = (dr - st + 1);
}

void update(int node, int st, int dr, int l, int r) {
    if(aint[node].sum == dr - st + 1){
        return;
    }
    propaga(node, st, dr);
    if(l <= st && dr <= r) {
        aint[node].lazy = 1;
        return;
    }
    int mid = (st + dr) / 2;
    if(aint[node].l == -1) {
        aint[node].l = ++nodes;
        aint[nodes].init();
    }
    if(aint[node].r == -1) {
        aint[node].r = ++nodes;
        aint[nodes].init();
    }
    if(l <= mid) {
        update(aint[node].l, st, mid, l, r);
    }
    if(r > mid) {
        update(aint[node].r, mid + 1, dr, l, r);
    }
    propaga(aint[node].l, st, mid);
    propaga(aint[node].r, mid + 1, dr);
    aint[node].sum = aint[aint[node].l].sum + aint[aint[node].r].sum;
}

int query(int node, int st, int dr, int l, int r) {
    propaga(node, st, dr);
  	if(aint[node].sum == 0) return 0;
    if(l <= st && dr <= r) {
        return aint[node].sum;
    }
    int mid = (st + dr) / 2;
    if(aint[node].l == -1) {
        aint[node].l = ++nodes;
        aint[nodes].init();
    }
    if(aint[node].r == -1) {
        aint[node].r = ++nodes;
        aint[nodes].init();
    }
    int sol = 0;
    if(l <= mid) {
        sol += query(aint[node].l, st, mid, l, r);
    }
    if(r > mid) {
        sol += query(aint[node].r, mid + 1, dr, l, r);
    }
    return sol;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    nodes = 1;
    aint[nodes].init();
    int q;
    cin >> q;
    int ans = 0;
    while(q--){
        int a, b, c;
        cin >> a >> b >> c;
        b += ans;
        c += ans;
        if(a == 2){
            update(1, 1, VMAX, b, c);
        }else{
            ans = query(1, 1, VMAX, b, c);
            cout << ans << "\n";
        }
    }
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	6 ms	1620 KB	Output is correct
5	Correct	7 ms	1908 KB	Output is correct
6	Correct	10 ms	1776 KB	Output is correct
7	Correct	8 ms	1892 KB	Output is correct
8	Correct	45 ms	12876 KB	Output is correct
9	Correct	81 ms	22220 KB	Output is correct
10	Correct	90 ms	24340 KB	Output is correct
11	Correct	102 ms	26040 KB	Output is correct
12	Correct	98 ms	26700 KB	Output is correct
13	Runtime error	121 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-