Submission #974227

#	Time	Username	Problem	Language	Result	Execution time	Memory
974227		happy_node	Seesaw (JOI22_seesaw)	C++17	1 / 100	2 ms	8540 KiB

seesaw

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int MX=2e5+5;

int N;
ll A[MX];

ld f(int l, int r) {
	return (ld)(A[r]-A[l-1])/(r-l+1);
}

vector<pair<ld,int>> v;

ld L[MX], R[MX];
int idL[MX], idR[MX];

struct fenwick {
	int t[2*MX];

	void upd(int pos, int val) {
		for(int i=pos;i<=2*N;i+=i&-i) t[i]+=val;
	}
	int que(int pos) {
		int res=0;
		for(int i=pos;i>0;i-=i&-i) res+=t[i];
		return res;
	}
	int que(int l, int r) {
		return que(r)-que(l-1);
	}
} fw;

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N;
	for(int i=1;i<=N;i++) {
		cin>>A[i];
		A[i]+=A[i-1];
	}

	// f(l,r) < f(l+1,r+1) < f(l+2,r+2) .... < 

	for(int k=1;k<=N;k++) {
		int l=k,r=N,res=0;
		while(l<=r) {
			int mid=(l+r)/2;
			if(f(mid-k+1,mid)>=f(1,N)) {
				res=mid,r=mid-1;
			} else {
				l=mid+1;
			}
		}

		// f(res-k,res-1) or f(res-k+1,res)
		L[k]=f(res-k,res-1);
		R[k]=f(res-k+1,res);
		v.push_back({L[k],k});
		v.push_back({R[k],k});
	}

	sort(v.begin(),v.end());

	int id=1;
	for(auto [x,k]:v) {
		if(x==L[k]) idL[k]=id;
		else idR[k]=id;
		id++;
	}

	for(int k=1;k<=N;k++) fw.upd(idL[k],1);

	ld ans=2e18;
	for(auto [x,k]:v) {
		int l=1,r=2*N,res=0;
		while(l<=r) {
			int mid=(l+r)/2;
			if(fw.que(mid)==N) {
				r=mid-1,res=mid;
			} else {
				l=mid+1;
			}
		}
		if(res!=0)
			ans=min(ans,v[res-1].first-x);
		if(x==L[k]) {
			fw.upd(idL[k],-1);
			fw.upd(idR[k],1);
		} else {

			fw.upd(idR[k],-1);
		}
	}

	cout<<fixed<<setprecision(10)<<ans<<'\n';

}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 33