Submission #334408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
334408	2020-12-09T06:10:42 Z	NhoxZuji	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	421 ms	144364 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 "main"

using namespace std;
typedef long long ll;

int n, cnt = 2;
struct node{
    int s, l, r, lid, rid, lazy;
    node() : s(0), lid(-1), rid(-1), lazy(0) {}
};

node st[3000005];

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

void newright(int id){
    if (st[id].rid == -1){
        st[id].rid = cnt++;
        st[st[id].rid].l = ((st[id].r + st[id].l) >> 1) + 1; st[st[id].rid].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;
    st[1].lazy = 0; st[1].s = 0;

    int c = 0;
    loop(n){
        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	42 ms	70764 KB	Output is correct
2	Correct	42 ms	70764 KB	Output is correct
3	Correct	42 ms	70764 KB	Output is correct
4	Correct	56 ms	70892 KB	Output is correct
5	Correct	64 ms	71020 KB	Output is correct
6	Correct	60 ms	71020 KB	Output is correct
7	Correct	59 ms	71020 KB	Output is correct
8	Correct	178 ms	71660 KB	Output is correct
9	Correct	334 ms	71916 KB	Output is correct
10	Runtime error	421 ms	144364 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Halted	0 ms	0 KB	-