Submission #1248071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248071		arashmemar	Food Court (JOI21_foodcourt)	C++20	21 / 100	230 ms	31976 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2.5e5 + 100;

struct Node
{
	int L, R, mid;
	long long int v, lazy, mn;
	Node *lc, *rc;

	Node (int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, v = lazy = mn = 0, lc = rc = NULL;
		return ;
	}

	void init()
	{
		if (R - L == 1)
		{
			return ;
		}
		lc = new Node(L, mid);
		rc = new Node(mid, R);
		lc->init();
		rc->init();
		return ;
	}

	void spread()
	{
		if (mn < -v)
		{
			v -= v + mn;
		}
		v += lazy;
		if (lc)
		{
			lc->mn = min(lc->mn, lc->lazy + mn);
			lc->lazy += lazy;
			rc->mn = min(rc->mn, rc->lazy + mn);
			rc->lazy += lazy;
		}
		lazy = 0;
		mn = 0;
		return ;
	}

	void update(int l, int r, long long int val)
	{
		spread();
		if (L == l and R == r)
		{
			lazy = mn = val;
			mn = min(val, 0ll);
			spread();
			return ;
		}
		if (l < mid)
		{
			lc->update(l, min(r, mid), val);
		}
		if (r > mid)
		{
			rc->update(max(l, mid), r, val);
		}
		return ;
	}

	long long int get(int p)
	{
		spread();
		if (R - L == 1)
		{
			return v;
		}
		if (p < mid)
		{
			return lc->get(p);
		}
		return rc->get(p);
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	Node *root = new Node(1, n + 1);
	root->init();
	while (q--)
	{
		int com;
		cin >> com;
		if (com == 1)
		{
			long long int l, r, c, k;
			cin >> l >> r >> c >> k;
			root->update(l, r + 1, k);
		}
		if (com == 2)
		{
			long long int l, r, k;
			cin >> l >> r >> k;
			root->update(l, r + 1, -k);
		}
		if (com == 3)
		{
			long long int a, b;
			cin >> a >> b;
			cout << (root->get(a) >= b) << '\n';			
		}
	}
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 21 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11