답안 #947803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947803	2024-03-17T03:45:55 Z	THXuan	원숭이와 사과 나무 (IZhO12_apple)	C++14	0 / 100	299 ms	262144 KB

apple

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
ll t[4 * MAXN], lazy[4 * MAXN], lf[4*MAXN], rg[4*MAXN];
int node_count = 1;

int create_node() {
    node_count++;
    return node_count;
}

void pushdown(int v, int l, int r) {
    int tm = (l + r) / 2;
    if (lf[v] == 0) lf[v] = create_node();
    if (rg[v] == 0) rg[v] = create_node();
    if (lazy[v]) {
        lazy[lf[v]] = 1;
        lazy[rg[v]] = 1;
        t[lf[v]] =  (tm - l + 1);
        t[rg[v]] = (r - tm);
        lazy[v] = 0;
    }
}
void upd(int v, int l, int r, int tl, int tr, ll val) {
    if (l > r)return;
    if (l == tl && r == tr) {
        lazy[v] = val;
        t[v] = (r - l + 1);
        return;
    }
    pushdown(v, tl, tr);
    int tm = (tl + tr) / 2;
    if (r <= tm) {
        if (lf[v] == 0) lf[v] = create_node();
        upd(lf[v], l, r, tl, tm, val);
    }
    else if (l >= tm + 1) {
        if (rg[v] == 0) rg[v] = create_node();
        upd(rg[v], l, r, tm + 1, tr, val);
    }
    else {
        if (lf[v] == 0) lf[v] = create_node();
        if (rg[v] == 0) rg[v] = create_node();
        upd(lf[v], l, tm, tl, tm, val);
        upd(rg[v], tm + 1, r, tm + 1, tr, val);
    }
    t[v] = t[lf[v]] + t[rg[v]] + lazy[v] * (tr - tl + 1);
}
ll query(int v, int tl, int tr, int l, int r) {
    if (l > r)return 0;
    if (l == tl && r == tr)return t[v];
    pushdown(v, tl, tr);
    int tm = (tl + tr) / 2;
    if (r <= tm)return query(lf[v], tl, tm, l, r);
    else if (l > tm)return query(rg[v], tm + 1, tr, l, r);
    else {
        ll left = query(lf[v], tl, tm, l, tm);
        ll right = query(rg[v], tm + 1, tr, tm + 1, r);
        return left + right;
    }
}

void solve()
{
    int m; cin >> m;
    int c = 0;
    while (m--) {
        int type; cin >> type;
        int l, r; cin >> l >> r;
        if (type == 1) {
            c = query(1, 1, 1000000005, l + c, r + c);
            cout << c << "\n";
        }
        else {
            upd(1, l + c, r + c, 1, 1000000005, 1);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;// cin>>t;
    while (t--) solve();
    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	8 ms	5468 KB	Output is correct
5	Correct	12 ms	7384 KB	Output is correct
6	Correct	9 ms	7512 KB	Output is correct
7	Correct	9 ms	7404 KB	Output is correct
8	Correct	69 ms	32080 KB	Output is correct
9	Correct	154 ms	53844 KB	Output is correct
10	Correct	168 ms	59272 KB	Output is correct
11	Correct	153 ms	62068 KB	Output is correct
12	Correct	163 ms	65152 KB	Output is correct
13	Correct	144 ms	74608 KB	Output is correct
14	Correct	141 ms	76452 KB	Output is correct
15	Runtime error	299 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-