Submission #783260

#	Time	Username	Problem	Language	Result	Execution time	Memory
783260		Dan4Life	Food Court (JOI21_foodcourt)	C++17	7 / 100	1056 ms	524288 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = 70000;
int n, m, q, tot[mxN];
deque<array<int,2>> shop[mxN];

void add(int i, int x, int v){
	if(sz(shop[i]) and shop[i].back()[0]==x)
		shop[i].back()[1]+=v,tot[i]+=v;
	else shop[i].pb({x,v}),tot[i]+=v;
} 

void rem(int i, int v){
	while(v and sz(shop[i])){
		if(shop[i][0][1]<=v) v-=shop[i][0][1],tot[i]-=shop[i][0][1], shop[i].pop_front();
		else shop[i][0][1]-=v, tot[i]-=v, v=0;
	}
}

int get(int i, int v){
	if(tot[i]<v) return 0; 
	int xd = 0;
	for(int j = 0; j < sz(shop[i]); j++){
		xd+=shop[i][j][1];
		if(xd>=v) return shop[i][j][0];
	}
	return 0;
}

int32_t main()
{
	cin >> n >> m >> q;
	while(q--){
		int t, l, r, x, v;
		cin >> t;
		if(t==1){
			cin >> l >> r >> x >> v;
			for(int i = l; i <= r; i++) add(i,x,v);
		}
		else if(t==2){
			cin >> l >> r >> v;
			for(int i = l; i <= r; i++) rem(i,v);
		}
		else cin >> x >> v, cout << get(x,v) << "\n";
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 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