Submission #567471

#	Time	Username	Problem	Language	Result	Execution time	Memory
567471		Drew_	Food Court (JOI21_foodcourt)	C++17	68 / 100	884 ms	43592 KiB

foodcourt

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

#define ll long long
#define mp make_pair
#define pb push_back
#define ii pair<int, int>
#define pl pair<ll, ll>
#define f1 first
#define s2 second

const int MAX = 250069;
const ll inf = 1e18 + 69;

struct Segtree1
{
	int n;
	ll st[1 << 19], lz1[1 << 19], lz2[1 << 19];

	Segtree1(int _n) : n(_n) {}
	inline void propagate(int node, int l, int r)
	{
		assert(node < (1 << 19));

		st[node] = max(st[node] + lz1[node], lz2[node]);
		if (l < r)
		{
			lz1[node << 1] += lz1[node];
			lz2[node << 1] += lz1[node];
			lz2[node << 1] = max(lz2[node << 1], lz2[node]);

			lz1[node << 1 | 1] += lz1[node];
			lz2[node << 1 | 1] += lz1[node];
			lz2[node << 1 | 1] = max(lz2[node << 1 | 1], lz2[node]);
		}
		lz1[node] = lz2[node] = 0;
	}

	inline void add(int p, int q, ll val)
	{
		const auto add_ = [&](const auto &self, int node, int l, int r) -> void
		{
			propagate(node, l, r);
			if (l > q || r < p)
				return;
			if (p <= l && r <= q)
			{
				lz1[node] += val; lz2[node] += val;
				propagate(node, l, r);
				return;
			}
			int mid = (l + r) >> 1;
			self(self, node << 1, l, mid);
			self(self, node << 1 | 1, mid+1, r);
			st[node] = max(st[node << 1], st[node << 1 | 1]);
		};
		add_(add_, 1, 1, n);
	}

	// Ai = max(Ai, val) for i in [p <= i <= q]
	inline void update(int p, int q, ll val)
	{
		const auto update_ = [&](const auto &self, int node, int l, int r) -> void
		{
			propagate(node, l, r);
			if (l > q || r < p)
				return;
			if (p <= l && r <= q)
			{
				lz2[node] = max(lz2[node], (ll)val);
				propagate(node, l, r);
				return;
			}
			int mid = (l + r) >> 1;
			self(self, node << 1, l, mid);
			self(self, node << 1 | 1, mid+1, r);
			st[node] = max(st[node << 1], st[node << 1 | 1]);
		};
		update_(update_, 1, 1, n);
	}

	inline ll query(ll p)
	{
		const auto query_ = [&](const auto &self, int node, int l, int r) -> ll
		{
			propagate(node, l, r);
			if (l > p || r < p)
				return -1;
			if (p <= l && r <= p)
				return st[node];
			int mid = (l + r) >> 1;
			return max(self(self, node << 1, l, mid), self(self, node << 1 | 1, mid+1, r));		
		};	
		return query_(query_, 1, 1, n);
	}
};

struct Segtree2
{
	int n;
	ll st[1 << 19], lz[1 << 19];

	Segtree2 (int _n) : n(_n) {}
	inline void propagate(int node, int l, int r)
	{
		assert(node < (1 << 19));

		st[node] += lz[node];
		if (l < r)
		{
			lz[node << 1] += lz[node];
			lz[node << 1 | 1] += lz[node];
		}
		lz[node] = 0;
	}

	inline void add(int p, int q, ll val)
	{
		const auto add_ = [&](const auto &self, int node, int l, int r) -> void
		{
			propagate(node, l, r);
			if (l > q || r < p)
				return;
			if (p <= l && r <= q)
			{
				lz[node] += val;
				propagate(node, l, r);
				return;
			}
			int mid = (l + r) >> 1;
			self(self, node << 1, l, mid);
			self(self, node << 1 | 1, mid+1, r);
			st[node] = min(st[node << 1], st[node << 1 | 1]);
		};
		add_(add_, 1, 0, n-1);
	}

	inline void modify(int p, ll val)
	{
		const auto modify_ = [&](const auto &self, int node, int l, int r) -> void
		{
			propagate(node, l, r);
			if (l > p || r < p)
				return;
			if (p <= l && r <= p)
			{
				st[node] = val;
				return;
			}

			int mid = (l + r) >> 1;
			self(self, node << 1, l, mid);
			self(self, node << 1 | 1, mid+1, r);
			st[node] = min(st[node << 1], st[node << 1 | 1]);
		};
		modify_(modify_, 1, 0, n-1);
	}

	inline int query()
	{
		const auto query_ = [&](const auto &self, int node, int l, int r) -> int
		{
			propagate(node, l, r);
			if (l == r)
				return l;

			int mid = (l + r) >> 1;
			propagate(node << 1, l, mid);
			if (st[node << 1] <= 0)
				return self(self, node << 1, l, mid);
			return self(self, node << 1 | 1, mid+1, r);
		};
		return query_(query_, 1, 0, n-1);
	}
};

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M, Q;
	cin >> N >> M >> Q;

	int ty[MAX], L[MAX], R[MAX];
	ll A[MAX], B[MAX];
	for (int i = 0; i < Q; ++i)
	{
		cin >> ty[i];
		if (ty[i] == 1) cin >> L[i] >> R[i] >> B[i] >> A[i];
		else if (ty[i] == 2) cin >> L[i] >> R[i] >> A[i];
		else cin >> A[i] >> B[i];
	}

	int askQ = 0;
	ll ans[MAX];
	vector<pair<pl, int>> query;

	Segtree1 st1(N), All(N);
	for (int i = 0; i < Q; ++i)
	{
		if (ty[i] == 1)
		{
			st1.add(L[i], R[i], A[i]);
			All.add(L[i], R[i], A[i]);
		}
		else if (ty[i] == 2)
		{
			st1.add(L[i], R[i], -A[i]);
			st1.update(L[i], R[i], 0);
		}
		else
		{
			ll cur = st1.query(A[i]);
			ll tot = All.query(A[i]);

			if (cur >= B[i]) query.pb({{A[i], tot - cur + B[i]}, askQ++});
			else ans[askQ++] = 0;
		}
	}

	sort(query.begin(), query.end());

	// cerr << "query: \n";
	// for (int i = 0; i < (int)query.size(); ++i)
	// 	cerr << query[i].f1.f1 << " " << query[i].f1.s2 << " " << query[i].s2 << '\n';
	// cerr << '\n';

	Segtree2 st2((int)query.size());
	for (int i = 0; i < (int)query.size(); ++i)
		st2.modify(i, query[i].f1.s2);

	for (int i = 0; i < Q; ++i)
	{
		if (ty[i] == 1)
		{
			int l = (int)(lower_bound(query.begin(), query.end(), mp(mp((ll)L[i], 0ll), 0)) - query.begin());
			int r = -1 + (int)(upper_bound(query.begin(), query.end(), mp(mp((ll)R[i], inf), 0)) - query.begin());
			
			if (l <= r)
				st2.add(l, r, -A[i]);
			
			while (st2.st[1] <= 0)
			{
				int id = st2.query();
				ans[query[id].s2] = B[i];
				st2.modify(id, inf);
			}
		}
	}

	for (int i = 0; i < askQ; ++i)
		cout << ans[i] << '\n';

	return 0;
}

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