Submission #1185008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185008		mychecksedad	Food Court (JOI21_foodcourt)	C++20	0 / 100	1101 ms	167340 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define vi vector<int>
#define en cout << '\n'
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define ll long long int
#define ff first
#define ss second
const int N = 250005, M = 1e6+5;


int n, m, q;
vector<array<ll, 3>> E[M], Q[M];
vi ans;
array<ll, 3> T[M], TT[M];

void rem(int l, int r, int ql, int qr, int k, ll num, int t){
	if(ql > r || l > qr) return;
	if(ql <= l && r <= qr){
		E[k].pb({t, num, -1});
		return;
	}
	int mid = l+r>>1;
	rem(l, mid, ql, qr, k<<1, num, t);
	rem(mid+1, r, ql, qr, k<<1|1, num, t);
}

void add(int l, int r, int ql, int qr, int k, int c, ll num, int t){
	if(ql > r || l > qr) return;
	if(ql <= l && r <= qr){
		E[k].pb({t, num, c});
		return;
	}
	int mid = l+r>>1;
	add(l, mid, ql, qr, k<<1, c, num, t);
	add(mid+1, r, ql, qr, k<<1|1, c, num, t);
}

void ADD(int l, int r, int p, int k, ll num, int C, bool flag){
	if(l == r){
		if(flag){
			T[k] = {0ll, num, C};
			TT[k] = {num, C};
		}else{
			T[k] = {0ll, 0ll, 0ll};
			TT[k] = {0ll, 0ll};
		}
		return;
	}
	int mid = l+r>>1;
	if(p <= mid) ADD(l, mid, p, k<<1, num, C, flag);
	else ADD(mid+1, r, p, k<<1|1, num, C, flag);

	if(T[k<<1][1] < T[k<<1|1][0]){
		T[k] = {T[k<<1][0] + (T[k<<1|1][0] - T[k<<1][1]), T[k<<1|1][1], (T[k<<1|1][2] != 0 ? T[k<<1|1][2] : T[k<<1][2])};
	}else{
		T[k] = {T[k<<1][0], T[k<<1][1] - T[k<<1|1][0] + T[k<<1|1][1], (T[k<<1|1][2] != 0 ? T[k<<1|1][2] : T[k<<1][2])};
	}
	TT[k][0] = TT[k<<1][0] + TT[k<<1|1][0];
}
void REM(int l, int r, int p, int k, ll num, bool flag){
	if(l == r){
		if(flag){
			T[k] = {num, 0ll, 0ll};
		}else{
			T[k] = {0ll, 0ll, 0ll};
		}
		return;
	}
	int mid = l+r>>1;
	if(p <= mid) REM(l, mid, p, k<<1, num, flag);
	else REM(mid+1, r, p, k<<1|1, num, flag);

	if(T[k<<1][1] < T[k<<1|1][0]){
		T[k] = {T[k<<1][0] + (T[k<<1|1][0] - T[k<<1][1]), T[k<<1|1][1], (T[k<<1|1][2] != 0 ? T[k<<1|1][2] : T[k<<1][2])};
	}else{
		T[k] = {T[k<<1][0], T[k<<1][1] - T[k<<1|1][0] + T[k<<1|1][1], (T[k<<1|1][2] != 0 ? T[k<<1|1][2] : T[k<<1][2])};
	}
		TT[k][0] = TT[k<<1][0] + TT[k<<1|1][0];

}

array<ll, 2> GET(int l, int r, int p, int k){
	if(l == r){
		return {T[k][0], T[k][1]};
	}
	int mid = l+r>>1;
	if(p <= mid) return GET(l, mid, p, k<<1);
	auto R = GET(mid+1, r, p, k<<1|1);
	if(T[k<<1][1] < R[0]){
		return array<ll,2>{T[k<<1][0] + R[0] - T[k<<1][1], R[1]};
	}
	return array<ll,2>{T[k<<1][0], R[1] - R[0] + T[k<<1][1]};
}

array<ll, 2> GETT(int l, int r, int p, int k, ll sum){ // {prefix erase, suffix take, id}
	int mid = l+r>>1;
	if(r <= p){
		if(l == r){
			if(TT[k][0] >= sum){
				return {sum, TT[k][1]};
			}
			return {TT[k][0], TT[k][1]};
		}
		if(TT[k<<1|1][0] >= sum){
			return GETT(mid+1, r, p, k<<1|1, sum);
		}
		return GETT(l, mid, p, k<<1, sum - TT[k<<1|1][0]);
	}else{
		if(p <= mid) return GETT(l, mid, p, k<<1, sum);

		auto R = GETT(mid+1, r, p, k<<1|1, sum);

		// cout << l << ' ' << r << ' ' << R[0] << ' ' << R[1] << ' ' << er << ' ' << sum << '\n';

		if(R[0] >= sum){
			return R;
		}
		if(TT[k<<1][0] + R[0] < sum){
			return {TT[k<<1][0] + R[0], 0ll};
		}

		return GETT(l, mid, p, k<<1, sum - R[0]);
	}
}

void dfs(int l, int r, int k){
	// add

	for(auto [t, num, C]: E[k]){
		// cout << "add: " <<l << ' ' << r << ' ' << t << ' ' << num << ' ' << C << '\n';
		if(C == -1){
			REM(1, q, t, 1, num, true);
		}else{
			ADD(1, q, t, 1, num, C, true);
		}
	}

	if(l < r){
		int mid = l+r>>1;
		dfs(l, mid, k<<1);
		dfs(mid+1, r, k<<1|1);
	}else{
		for(auto [b, t, idx]: Q[l]){
			// cout << l << ' ' << b << ' ' << t << '\n';
			ll sum = GET(1, q, t, 1)[1];
			if(sum < b) ans[idx] = 0;
			else{
				ans[idx] = GETT(1, q, t, 1, sum - b + 1)[1];
			}
		}
	}

	// pop

	for(auto [t, num, C]: E[k]){

		// cout << "rem: " <<l << ' ' << r << ' ' << t << ' ' << num << ' ' << C << '\n';
		if(C == -1){
			REM(1, q, t, 1, num, false);
		}else{
			ADD(1, q, t, 1, num, C, false);
		}
	}
}


void solve(){
	cin >> n >> m >> q;
	for(int i = 1; i <= q; ++i){
		int tp; cin >> tp;
		if(tp == 1){
			int l, r, c; ll k; cin >> l >> r >> c >> k;
			add(1, n, l, r, 1, c, k, i);
		}else if(tp == 2){
			int l, r;
			ll k; cin >> l >> r >> k;
			rem(1, n, l, r, 1, k, i);
		}else{
			ll v, b; cin >> v >> b;
			Q[v].pb({b, i, (int)ans.size()});
			ans.pb(0);
		}
	}

	for(int j = 0; j <= 4*q; ++j) T[j] = {0ll};
	for(int j = 0; j <= 4*q; ++j) TT[j] = {0ll};

	dfs(1, n, 1); 


	for(int i = 0; i < ans.size(); ++i) cout << ans[i] << '\n';
}

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	return 0;
}

• 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