Submission #1248138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248138		arashmemar	Food Court (JOI21_foodcourt)	C++20	21 / 100	522 ms	119172 KiB

foodcourt

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

const int maxn = 2.5e5 + 100;
const long long int inf = 1e18;

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

	Node (int l, int r)
	{
		L = l, R = r, mid = (L + R) / 2, v = lazy = mn = s = 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)
		{
			if (val > 0)
			{
				s += val;
			}
			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 ;
	}

	pair <long long int, long long int> get(int p)
	{
		spread();
		if (R - L == 1)
		{
			return {v, s};
		}
		pair <long long int, long long int> ret;
		if (p < mid)
		{
			ret = lc->get(p);
			ret.second += s;
			return ret;
		}
		ret = rc->get(p);
		ret.second += s;
		return ret;
	}
};

vector <pair <int, pair <pair <int, int>, pair <int, long long int>>>> qs;
int ans[maxn];

struct S
{
	int L, R, mid;
	long long int v, lazy, mv;
	S *lc, *rc;
	set <pair <long long int, int>> s;

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

	void init()
	{
		if (R - L == 1)
		{
			s.insert({inf, 0});
			return ;
		}
		lc = new S(L, mid);
		rc = new S(mid, R);
		lc->init();
		rc->init();
		return ;
	}

	void spread()
	{
		v -= lazy;
		mv -= lazy;
		if (lc)
		{
			lc->lazy += lazy;
			rc->lazy += lazy;
		}
		lazy = 0;
		return ;
	}

	void update(int p, pair <long long int, int> val, bool del)
	{
		spread();
		if (R - L == 1)
		{
			if (del)
			{
				s.erase(val);
			}
			else
			{
				s.insert(val);
			}
			v = (*s.begin()).first - mv;
			return ;
		}
		if (p < mid)
		{
			lc->update(p, val, del);
		}
		else
		{
			rc->update(p, val, del);
		}
		lc->spread();
		rc->spread();
		v = min(lc->v, rc->v);
		return ;
	}

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

	int get()
	{
		spread();
		if (R - L == 1)
		{
			int tmp = (*s.begin()).second;
			s.erase(s.begin());
			v = (*s.begin()).first - mv;
			return tmp;

		}
		int ret;
		lc->spread();
		rc->spread();
		if (lc->v <= 0)
		{
			ret = lc->get();
		}
		else
		{
			ret = rc->get();
		}
		v = min(lc->v, rc->v);
		return ret;
	}
};


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();
	S *root2 = new S(1, n + 1);
	root2->init();
	int noq = 0;
	for (int i = 1;i <= q;i++)
	{
		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);
			qs.push_back({com, {{l, r}, {c, 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;
			pair <long long int, long long int> tmp = root->get(a);
			noq++;
			if (b <= tmp.first)
			{
				cout << 1 << endl;
				root2->update(a, {tmp.second - tmp.first + b, noq}, 0);
			}
			else
			{
				cout << 0 << endl;
			}
		}
	}

	return 0;

	for (auto o : qs)
	{
		int com = o.first, l = o.second.first.first, r = o.second.first.second, c = o.second.second.first;
		long long int k = o.second.second.second;
		root2->update(l, r + 1, k);
		while (root2->v <= 0)
		{
			ans[root2->get()] = c;
		}
	}
	for (int i = 1;i <= noq;i++)
	{
		cout << ans[i] << '\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