Submission #711775

#	Time	Username	Problem	Language	Result	Execution time	Memory
711775		minhcool	Food Court (JOI21_foodcourt)	C++17	100 / 100	518 ms	91316 KiB

foodcourt

#include<bits/stdc++.h>
 
using namespace std; 
 
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
 
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 4e5 + 5, MAXN = 1e7 + 5;
 
const long long oo = 1e9 + 7, mod = 1e9 + 7;
 
/*
upd[]: content of ith update
in[] -> if the ith query is in the segtree
ques[] -> queries that begin/end at i
ask[] -> "service" queries
*/
 
int n, m, q;
 
ii upd[N];
bool in[N];
vector<int> ques[N];
vector<ii> ask[N];
 
struct node{
	int mn_pref = oo, mn_pos = 0;
	int tol_plus = 0, tol_minus = 0;
	node(){}
};
 
node IT[N << 2];
 
node merge(node a, node b){
	node c;
	c.mn_pref = min(a.mn_pref, a.tol_plus - a.tol_minus + b.mn_pref);
	c.mn_pos = ((c.mn_pref == a.mn_pref) ? a.mn_pos : b.mn_pos); 
	c.tol_plus = a.tol_plus + b.tol_plus;
	c.tol_minus = a.tol_minus + b.tol_minus;
	return c;
}
 
void update(int id, int l, int r, int pos, bool add){
	if(l == r){
		//cout << l << " " << r << " " << pos << " " << id << "\n";
		IT[id].mn_pref = IT[id].tol_plus = IT[id].tol_minus = 0;
		IT[id].mn_pos = l;
		if(!add) return;
		if(upd[pos].se == 0){
			IT[id].mn_pref = -upd[pos].fi;
			IT[id].tol_minus = upd[pos].fi;
		}
		else{
			IT[id].mn_pref = upd[pos].fi;
			IT[id].tol_plus = upd[pos].fi;
		}
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= pos) update(id << 1, l, mid, pos, add);
	else update(id << 1 | 1, mid + 1, r, pos, add);
	IT[id] = merge(IT[id << 1], IT[id << 1 | 1]);
}
 
node zero;
 
node get(int id, int l, int r, int L, int R){
	if(l > R || r < L) return zero;
	if(l >= L && r <= R) return IT[id];
	int mid = (l + r) >> 1;
	return merge(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R));
}
 
int bins(int id, int l, int r, int rem){
	if(l == r){
		if(rem > IT[id].tol_plus) return -1;
		return l;
	}
	int mid = (l + r) >> 1;
	if(IT[id << 1].tol_plus >= rem) return bins(id << 1, l, mid, rem);
	else return bins(id << 1 | 1, mid + 1, r, rem - IT[id << 1].tol_plus);
}
 
int ans[N];
 
void process(){
	cin >> n >> m >> q;
	for(int i = 1; i <= q; i++){
		int t, l, r, k, c = 0, a, b;
		cin >> t;
		if(t == 1) cin >> l >> r >> c >> k;
		else if(t == 2) cin >> l >> r >> k;
		else cin >> a >> b;
		//cout << t << "\n";
		if(t <= 2){
			upd[i] = {k, c};
			ques[l].pb(i);
			ques[r + 1].pb(i);
		}
		else{
			ask[a].pb({i, b});
		}
	}
	//cout << "OK\n";
	//return;
	for(int i = 1; i <= n; i++){
		for(auto it : ques[i]){
			//continue;
			in[it] ^= 1;
			update(1, 1, q, it, in[it]);
		}
		//for(int j = 1; j <= q; j++) cout << get(1, 1, q, j, j).tol_plus << "\n";
		for(auto it : ask[i]){
			//continue;
			node temp = get(1, 1, q, 1, it.fi);
			if(temp.mn_pref > 0){
				temp.mn_pref = temp.mn_pos = 0;
			}
			//cout << temp.mn_pos << "\n";
			//cout << i << " " << it.fi << " " << temp.tol_plus << " " << temp.tol_minus << "\n";
			node temp2 = get(1, 1, q, temp.mn_pos + 1, it.fi);
			int tol_pluss = temp.tol_plus - temp2.tol_plus;
			int posi = bins(1, 1, q, it.se + tol_pluss + temp2.tol_minus);
			//cout << it.se << " " << tol_pluss << " " << temp2.tol_minus << "\n";
			if(posi < 0 || posi > it.fi) ans[it.fi] = 0;
			else ans[it.fi] = upd[posi].se;
		}
	}
	for(int i = 1; i <= q; i++){
		if(upd[i].fi) continue;
		cout << ans[i] << "\n";
	}
}
 
signed main(){
	ios_base::sync_with_stdio(0);
 
	#ifdef nqm
		freopen("input.inp", "r", stdin);
		freopen("output.out", "w", stdout);
	#endif
	#ifndef nqm
		
	#endif
 
	process();
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11