Submission #1206840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206840		emptypringlescan	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	0 / 100	53 ms	2376 KiB

mizuyokan2

#include <bits/stdc++.h>
using namespace std;
int n,q;
long long arr[250005];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> arr[i];
	cin >> q;
	while(q--){
		int a;
		long long b;
		int c,d;
		cin >> a >> b >> c >> d;
		c++;
		arr[a]=b;
		vector<pair<int,long long> > yay;
		int ans=1;
		bool broke=false;
		yay.push_back({c,arr[c]});
		long long pref=arr[c];
		for(int i=c+1; i<=d; i++){
			pref+=arr[i];
			if(broke&&pref-yay.back().second-arr[i]<=arr[yay.back().first]){
				if(pref+arr[i]<yay.back().second+arr[yay.back().first]) yay.push_back({i,pref});
				continue;
			}
			int lo=0,hi=yay.size()-1,mid;
			while(lo<hi){
				mid=(lo+hi)/2;
				if(pref-yay[mid].second-arr[i]>arr[yay[mid].first]) hi=mid;
				else lo=mid+1;
			}
			if(pref-yay[lo].second-arr[i]>arr[i]){
				yay.clear();
				yay.push_back({i,pref});
				ans+=2;
				broke=true;
			}
		}
		for(auto i:yay){
			if(pref-i.second>arr[i.first]){
				ans++;
				break;
			}
		}
		
		yay.clear();
		pref=arr[c];
		int ans2=0;
		for(int i=c+1; i<=d; i++){
			pref+=arr[i];
			if(pref-arr[i]<=arr[i]) continue;
			if(yay.empty()){
				yay.push_back({i,pref});
				ans2=2;
				continue;
			}
			if(pref-yay.back().second-arr[i]<=arr[yay.back().first]){
				if(pref+arr[i]<yay.back().second+arr[yay.back().first]) yay.push_back({i,pref});
				continue;
			}
			int lo=0,hi=yay.size()-1,mid;
			while(lo<hi){
				mid=(lo+hi)/2;
				if(pref-yay[mid].second-arr[i]>arr[yay[mid].first]) hi=mid;
				else lo=mid+1;
			}
			if(pref-yay[lo].second-arr[i]>arr[i]){
				yay.clear();
				yay.push_back({i,pref});
				ans2+=2;
			}
		}
		for(auto i:yay){
			if(pref-i.second>arr[i.first]){
				ans2++;
				break;
			}
		}
		cout << max(ans,ans2) << '\n';
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11