Submission #735520

#	Time	Username	Problem	Language	Result	Execution time	Memory
735520		QwertyPi	Food Court (JOI21_foodcourt)	C++14	21 / 100	616 ms	77908 KiB

foodcourt

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

struct np{
	int x = 0, y = 0;
	np() {};
	np(int v){
		if(v >= 0) x = 0, y = v;
		else x = -v, y = 0;
	}
	np(int x, int y) : x(x), y(y){
	}
	friend np operator+ (const np& a, const np& b) {
		return {a.x + b.x - min(a.y, b.x), a.y + b.y - min(a.y, b.x)};
	}
};

struct node{
	np acc;
	int sum = 0, psum = 0, nsum = 0, colour = 0;
	friend void add(node& res, const node& L, const node& R){
		res.acc = L.acc + R.acc;
		res.sum = L.sum + R.sum;
		res.psum = L.psum + R.psum;
		res.nsum = L.nsum + R.nsum;
	}
};

const int N_MAX = 2.5e5 + 11;

node t[N_MAX << 2];

void assign(int idx, int k, int c = 0, int v = 0, int tl = 0, int tr = N_MAX - 1){
	if(tl == tr){
		t[v].acc = np(k);
		t[v].sum = k;
		t[v].nsum = k < 0 ? k : 0;
		t[v].psum = k > 0 ? k : 0;
		t[v].colour = c;
		return;
	}
	int tm = (tl + tr) / 2;
	if(idx <= tm){
		assign(idx, k, c, v * 2 + 1, tl, tm);
	}else{
		assign(idx, k, c, v * 2 + 2, tm + 1, tr);
	}
	add(t[v], t[v * 2 + 1], t[v * 2 + 2]);
}

int bs(int k, int v = 0, int tl = 0, int tr = N_MAX - 1){
	if(tl == tr) return tl;
	int tm = (tl + tr) / 2;
	if(t[v * 2 + 1].psum >= k){
		return bs(k, v * 2 + 1, tl, tm);
	}else{
		return bs(k - t[v * 2 + 1].psum, v * 2 + 2, tm + 1, tr);
	}
}

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

np qry(int r, int v = 0, int tl = 0, int tr = N_MAX - 1){
	if(tl == tr) return t[v].acc;
	int tm = (tl + tr) / 2;
	if(r <= tm){
		return qry(r, v * 2 + 1, tl, tm);
	}else{
		return t[v * 2 + 1].acc + qry(r, v * 2 + 2, tm + 1, tr);
	}
}

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

vector<query> Q;
int C[N_MAX];

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, c, 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;
		}
		C[i] = Q.back().c; 
	}
	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) assign(q.i, q.k, q.c);
		else {
			auto acc = qry(q.i);
			if(acc.y < q.k){
				ans[q.i] = 0;
			}else{
				ans[q.i] = 1;
			}
		}
	}
	for(auto [i, j] : ans){
		cout << j << endl;
	}
}

Compilation message (stderr)

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

• 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