Submission #426058

#	Time	Username	Problem	Language	Result	Execution time	Memory
426058		8e7	Food Court (JOI21_foodcourt)	C++14	21 / 100	582 ms	47828 KiB

foodcourt

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){ cout << a << " ";debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 250005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
//using namespace __gnu_pbds;

struct segtree{
	ll seg[4 * maxn], tag[4 * maxn];
	void modify(int cur, int l, int r, int ql, int qr, ll val) {
		if (r <= l || qr <= l || ql >= r) return;
		if (ql <= l && qr >= r) {
			tag[cur] += val;
			return;
		}
		int mid = (l + r) / 2;
		modify(cur * 2, l, mid, ql, qr, val);
		modify(cur * 2 + 1, mid, r, ql, qr, val);
		seg[cur] = min(seg[cur * 2] + tag[cur * 2], seg[cur * 2 + 1] + tag[cur * 2 + 1]);
	}
	ll query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || qr <= l || ql >= r) return 1LL<<60;
		if (ql <= l && qr >= r) return seg[cur] + tag[cur];
		int mid = (l + r) / 2;
		return tag[cur] + min(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));	
	}
} se;
vector<pii> query[maxn], mod[maxn], arr[maxn]; 
int col[maxn];
ll ans[maxn];
int main() {
	io
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> qind;
	for (int i = 0;i < q;i++) {
		int type;
		cin >> type;
		if (type == 1) {
			ll l, r, c, k;
			cin >> l >> r >> c >> k;
			col[i] = c;
			arr[l].push_back({i, k});
			arr[r + 1].push_back({i, -k});
			mod[l].push_back({i, k});
			mod[r + 1].push_back({i, -k});
		} else if (type == 2) {
			ll l, r, k;
			cin >> l >> r >> k;
			mod[l].push_back({i, -k});
			mod[r + 1].push_back({i, k});
		} else {
			ll ind, num;
			cin >> ind >> num;
			query[ind].push_back({i, num});
			qind.push_back(i);
		}
	}
	for (int i = 1;i <= n;i++) {
		for (auto j:mod[i]) {
			se.modify(1, 0, q, j.ff, q, j.ss);			
		}
		for (auto j:query[i]) {
			ll val = min(0LL, se.query(1, 0, q, 0, j.ff + 1));
			ll pnt = se.query(1, 0, q, j.ff, j.ff + 1);
			//debug(j.ff, j.ss, pnt, val);
			if (pnt - val >= j.ss) {
				ans[j.ff] = 1;
			} else {
				ans[j.ff] = 0;
			}
		}
	}
	for (int i:qind) {
		cout << ans[i] << "\n";
	}
}
/*
3 4 7
1 1 2 1 1
1 1 3 4 1
2 2 3 1
2 1 3 1
1 1 2 2 1
3 1 1
3 3 2

4 1 7
1 1 3 1 5
1 2 4 1 3
2 1 3 5 
1 3 4 1 7
3 3 4
3 2 3
3 1 1
   */

• 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