Submission #735353

#	Time	Username	Problem	Language	Result	Execution time	Memory
735353		QwertyPi	Food Court (JOI21_foodcourt)	C++14	0 / 100	1069 ms	48416 KiB

foodcourt

#include <bits/stdc++.h>
#define int long long
#define INF (1LL << 60)
using namespace std;

struct node{
	node(){ };
	node(int k, int c) { pmax = sum = k; colour = c; }
	int pmax = -INF, sum = 0, colour = 0;
	friend node operator+ (const node& L, const node& R){
		node res;
		res.pmax = max(L.pmax, L.sum + R.pmax);
		res.sum = L.sum + R.sum;
		return res;
	}
};

const int N_MAX = 2.5e5 + 11;

node t[N_MAX << 2];

void add(int idx, int k, int c = 0, int v = 0, int tl = 0, int tr = N_MAX - 1){
	// if(v == 0) cout << "ADD " << idx << ' ' << k << ' ' << c << endl;
	if(tl == tr){
		t[v] = node(k, c);
		return;
	}
	int tm = (tl + tr) / 2;
	if(idx <= tm){
		add(idx, k, c, v * 2 + 1, tl, tm);
	}else{
		add(idx, k, c, v * 2 + 2, tm + 1, tr);
	}
	t[v] = t[v * 2 + 1] + t[v * 2 + 2];
}

int qry(int idx, int k, int v = 0, int tl = 0, int tr = N_MAX - 1){
	// if(v == 0) cout << "QRY " << idx << ' ' << k << endl;
	if(tl == tr) return t[v].pmax >= k ? t[v].colour : 0;
	int tm = (tl + tr) / 2;
	if(idx <= tm){
		return qry(idx, k, v * 2 + 1, tl, tm);
	}else{
		int q1 = qry(idx, k, v * 2 + 1, tl, tm);
		int q2 = qry(idx, k - t[v * 2 + 1].sum, v * 2 + 2, tm + 1, tr);
		// cout << q1 << ' ' << q2 << endl;
		return q2 ? q2 : q1;
	}
}


int sum(int idx, int v = 0, int tl = 0, int tr = N_MAX - 1){
	if(tl == tr) return t[v].sum;
	int tm = (tl + tr) / 2;
	if(idx <= tm){
		return sum(idx, v * 2 + 1, tl, tm);
	}else{
		int q1 = sum(idx, v * 2 + 1, tl, tm);
		int q2 = sum(idx, v * 2 + 2, tm + 1, tr);
		return q1 + q2;
	}
}

struct query{
	int p, i, t, c, k;
};

vector<query> Q;
int32_t main(){
	cin.tie(0);
	cout.tie(0)->sync_with_stdio(false);
	int n, m, q; cin >> n >> m >> q;
	for(int i = 0; i < q; i++){
		int l, r, a, c, k;
		int t; cin >> t;
		switch(t){
			case 1: t = 1; cin >> l >> r >> c >> k; Q.push_back({l, i, 1, c, k}); Q.push_back({r + 1, i, 1, 0, 0}); break;
			case 2: t = 2; cin >> l >> r >> k; Q.push_back({l, i, 1, 0, -k}); Q.push_back({r + 1, i, 1, 0, 0}); break;
			case 3: t = 3; cin >> a >> k; Q.push_back({a, i, 2, 0, k}); break;
		}
	}
	sort(Q.begin(), Q.end(), [](query a, query b){
		return a.p < b.p || a.p == b.p && a.i < b.i;
	});
	map<int, int> ans;
	for(auto& q : Q){
		if(q.t == 1) add(q.i, q.k, q.c);
		else {
			ans[q.i] = sum(q.i) >= q.k ? 1 : 0;
		}
	}
	for(auto [i, j] : ans){
		cout << j << endl;
	}
}

Compilation message (stderr)

foodcourt.cpp: In lambda function:
foodcourt.cpp:83:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   83 |   return a.p < b.p || a.p == b.p && a.i < b.i;
      |                       ~~~~~~~~~~~^~~~~~~~~~~~
foodcourt.cpp: In function 'int32_t main()':
foodcourt.cpp:92:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |  for(auto [i, j] : ans){
      |           ^

• 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