oj.uz

답안 #567466

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567466 2022-05-23T14:28:54 Z Drew_ 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 456 ms 25088 KB 
#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)
	{
		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)
	{
		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);
	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';

			// if (st1.query(A[i]) >= B[i]) query.pb({{A[i], st1.query(A[i]) - B[i]}, askQ++});
			// else ans[askQ++] = 0;
		}
	}
	return 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(N);
	for (int i = Q-1, j = (int)query.size()-1; i >= 0; --i)
	{
		if (ty[i] <= 2)
		{
			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());
			
			cerr << L[i] << " " << R[i] << " " << l << " " << r << '\n';

			if (l <= r)
			{
				if (ty[i] == 1) st2.add(l, r, -A[i]);
				else st2.add(l, r, A[i]);
			}

			while (st2.st[1] < 0)
			{
				cerr << "i: " << i << '\n';

				int id = st2.query();
				ans[query[id].s2] = B[i];
				st2.modify(id, inf);
			}
		}
		else
		{
			int id = (int)(lower_bound(query.begin(), query.end(), mp(mp(A[i], B[i]), j--)) - query.begin());
			st2.modify(id, B[i]);
		}
	}

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

	return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 20664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 456 ms 25088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 73 ms 20912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 19496 KB Output isn't correct
2 Halted 0 ms 0 KB -