Submission #421715

#	Time	Username	Problem	Language	Result	Execution time	Memory
421715		pavement	Food Court (JOI21_foodcourt)	C++17	0 / 100	887 ms	524292 KiB

foodcourt

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<iii, null_type, greater<iii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int N, M, Q, T, L, R, C, K, A, B;

struct node {
	node *left, *right;
	int S, E;
	queue<pair<bool, int> > val;
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void prop() {
		if (S == E) return;
		while (!val.empty()) {
			auto [tmp1, tmp2] = val.front();
			val.pop();
			left->val.emplace(tmp1, tmp2);
			right->val.emplace(tmp1, tmp2);
		}
	}
	void upd(int l, int r, int v, bool t = 0) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val.emplace(t, v);
			return;
		}
		prop();
		left->upd(l, r, v, t);
		right->upd(l, r, v, t);
	}
	int qry(int p) {
		if (S == E) {
			int tmp = 0;
			while (!val.empty()) {
				auto [tmp1, tmp2] = val.front();
				val.pop();
				if (tmp1) tmp = max(0ll, tmp);
				else tmp += tmp2;
			}
			val.emplace(0, tmp);
			return tmp;
		}
		int M = (S + E) >> 1;
		prop();
		if (p <= M) return left->qry(p);
		else return right->qry(p);
	}
} *root;

struct node2 {
	node2 *left, *right;
	int S, E, val, pv;
	node2(int _s, int _e) : S(_s), E(_e), val(0), pv(0) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node2(S, M);
		right = new node2(M + 1, E);
	}
	void prop() {
		if (S == E || !pv) return;
		left->val = left->pv = right->val = right->pv = pv;
		pv = 0;
	}
	void upd(int l, int r, int k) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			val = pv = k;
			return;
		}
		prop();
		left->upd(l, r, k);
		right->upd(l, r, k);
	}
	int qry(int p) {
		if (S == E) return val;
		int M = (S + E) >> 1;
		prop();
		if (p <= M) return left->qry(p);
		else return right->qry(p);
	}
} *root2;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M >> Q;
	root = new node(1, N);
	root2 = new node2(1, N);
	for (int i = 1; i <= Q; i++) {
		cin >> T;
		if (T == 1) {
			cin >> L >> R >> C >> K;
			root->upd(L, R, K);
			root2->upd(L, R, C);
		} else if (T == 2) {
			cin >> L >> R >> K;
			root->upd(L, R, -K);
			root->upd(L, R, 0, 1);
		} else {
			cin >> A >> B;
			cout << (root->qry(A) >= B ? 1 : 0) << '\n';
		}
	}
}

Compilation message (stderr)

foodcourt.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main() {
      | ^~~~

• 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