Submission #957947

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
957947	2024-04-04T14:03:42 Z	bmh123456789asdf	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 ms	185940 KB

apple

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

struct Node {
	int sum, lazy, tl, tr, l, r;
	Node() : sum(0), lazy(0), l(-1), r(-1) {}
};

const int MAXN = 123456;
Node segtree[64 * MAXN];
int cnt = 2;

void pushlazy(int node)
{
    	if (segtree[node].lazy) {
		segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}
		segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
		segtree[node].lazy = 0;
	}
}

void update(int node, int l, int r) {
	pushlazy(node);
	if (l == segtree[node].tl && r == segtree[node].tr) {
		segtree[node].lazy = 1;
		pushlazy(node);
	} else {
		int mid = (segtree[node].tl + segtree[node].tr) / 2;
		if (segtree[node].l == -1) {
			segtree[node].l = cnt++;
			segtree[segtree[node].l].tl = segtree[node].tl;
			segtree[segtree[node].l].tr = mid;
		}
		if (segtree[node].r == -1) {
			segtree[node].r = cnt++;
			segtree[segtree[node].r].tl = mid + 1;
			segtree[segtree[node].r].tr = segtree[node].tr;
		}

		if (l > mid) update(segtree[node].r, l, r);
		else if (r <= mid) update(segtree[node].l, l, r);
		else {
			update(segtree[node].l, l, mid);
			update(segtree[node].r, mid + 1, r);
		}

		pushlazy(segtree[node].l);
		pushlazy(segtree[node].r);
		segtree[node].sum =
		    segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
	}
}


int query(int node,int l,int r)
{
    pushlazy(node);
    if(l == segtree[node].tl && r == segtree[node].tr) return segtree[node].sum;
    else
    {
        int mid = (segtree[node].tr + segtree[node].tl) / 2;
        if(segtree[node].l == -1)
        {
            segtree[node].l = cnt++;
            segtree[cnt].tl = segtree[node].tl;
            segtree[cnt].tr = mid;
        }
        if(segtree[node].r == -1)
        {
            segtree[node].r = cnt++;
            segtree[cnt].tl = mid + 1;
            segtree[cnt].tr = segtree[node].tr;
        }

        if(l > mid) return query(segtree[node].r, l, r);
        else if(r <= mid) return query(segtree[node].l, l, r);
        else return query(segtree[node].l, l, mid) + query(segtree[node].r, mid + 1, r);
    }
}


int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	int m;
	cin >> m;

	segtree[1].sum = 0;
	segtree[1].lazy = 0;
	segtree[1].tl = 1;
	segtree[1].tr = 1e9;

	int c = 0;
	FOR(_, 0, m) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			c = query(1, x + c, y + c);
			cout << c << '\n';
		} else update(1, x + c, y + c);
	}
	return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	185940 KB	Output is correct
2	Execution timed out	2079 ms	185872 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-