Submission #566885

#	Time	Username	Problem	Language	Result	Execution time	Memory
566885		Drew_	Food Court (JOI21_foodcourt)	C++17	0 / 100	100 ms	18712 KiB

foodcourt

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

#define ll long long

const int MAX = 250069;

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)
	{
		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, int 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], 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, int 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], st[node << 1 | 1]);
		};
		update_(update_, 1, 1, n);
	}

	inline ll query(int 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);
	}
};

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], 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];
	}

	Segtree1 st1(N);
	for (int i = 0; i < Q; ++i)
	{
		if (ty[i] == 1)
		{
			st1.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
		{
			if (st1.query(A[i]) >= B[i]) cout << 1 << '\n';
			else cout << 0 << '\n';	
		}
	}

	return 0;
}

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