Submission #334397

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
334397	2020-12-09T05:52:14 Z	NhoxZuji	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	565 ms	262144 KB

apple

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define eb emplace_back
#define pb push_back
#define pf push_front
#define mp make_pair
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pdd pair<double, double>
#define fi first
#define se second
#define fr(x, y, z) for (int x = y; x <= z; ++x)
#define loop(x) while(x--)
#define read(x)  freopen(x".INP","r",stdin);
#define write(x) freopen(x".OUT","w",stdout);
#define nametask "f"

using namespace std;
typedef long long ll;

int n, cnt = 1;
struct node{
    int s, l, r, lid, rid, lazy;
    node() : s(0), lid(-1), rid(-1), lazy(0) {}
};
int const maxn = 1e6 + 5;
node st[6 * maxn];

void newleft(int id){
    if (st[id].lid == -1){
        int nod;
        st[id].lid = nod = ++cnt;
        st[nod].l = st[id].l; st[nod].r = (st[id].r + st[id].l) >> 1;
    }
}

void newright(int id){
    if (st[id].rid == -1){
        int nod;
        st[id].rid = nod = ++cnt;
        st[nod].l = ((st[id].r + st[id].l) >> 1) + 1; st[nod].r = st[id].r;
    }
}

void plazy(int id){
    if (st[id].lazy){
        newleft(id); newright(id);
        st[id].s = st[id].r - st[id].l + 1;
        st[st[id].lid].lazy = st[st[id].rid].lazy = 1;
        st[id].lazy = 0;
    }
}

void upd(int id, int l, int r){
    plazy(id);
    if (st[id].l == l && st[id].r == r){
        st[id].lazy = 1;
        plazy(id);
    } else
    {
        newleft(id); newright(id);
        int mid = (st[id].l + st[id].r) >> 1;
        if (l > mid)  upd(st[id].rid, l, r); else
        if (r <= mid) upd(st[id].lid, l, r); else{
            upd(st[id].lid, l, mid);
            upd(st[id].rid, mid + 1, r);
        }

        plazy(st[id].lid); plazy(st[id].rid);
        st[id].s = st[st[id].lid].s + st[st[id].rid].s;
    }
}

int query(int id, int l, int r){
    plazy(id);
    if (st[id].l == l && st[id].r == r) return st[id].s; else
    {
        newleft(id); newright(id);
        int mid = (st[id].l + st[id].r) >> 1;
        if (l > mid)  return query(st[id].rid, l, r); else
        if (r <= mid) return query(st[id].lid, l, r); else
        return query(st[id].lid, l, mid) + query(st[id].rid, mid + 1, r);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //read(nametask); write(nametask);
    cin >> n;
    st[1].l = 1; st[1].r = (int) 1e9;

    int c = 0;
    for (int i = 1; i <= n; ++i){
        int d, x, y;
        cin >> d >> x >> y;
        if (d == 1){
            c = query(1, x + c, y + c);
            cout << c << "\n";
        } else upd(1, x + c, y + c);
    }
    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	81 ms	141292 KB	Output is correct
2	Correct	83 ms	141292 KB	Output is correct
3	Correct	83 ms	141292 KB	Output is correct
4	Correct	107 ms	141420 KB	Output is correct
5	Correct	97 ms	141420 KB	Output is correct
6	Correct	102 ms	141420 KB	Output is correct
7	Correct	98 ms	141736 KB	Output is correct
8	Correct	225 ms	142316 KB	Output is correct
9	Correct	372 ms	143340 KB	Output is correct
10	Correct	404 ms	143468 KB	Output is correct
11	Correct	392 ms	143468 KB	Output is correct
12	Correct	415 ms	143488 KB	Output is correct
13	Correct	344 ms	143852 KB	Output is correct
14	Correct	368 ms	143892 KB	Output is correct
15	Runtime error	565 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Halted	0 ms	0 KB	-