Submission #974270

#	Time	Username	Problem	Language	Result	Execution time	Memory
974270		happy_node	Seesaw (JOI22_seesaw)	C++17	100 / 100	169 ms	29376 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];
	}

	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)
		if(res-k<1)
			L[k]=f(res-k+1,res);
		else
			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(!idL[k]) idL[k]=id;
		else idR[k]=id;
		id++;
	}

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

	/* 

	each k adds 2 important point f(l,l+k-1) or f(l+1,l+k) 
	for some l s.t. f(l,l+k-1) <= f(1,N) <= f(l+1,l+k)

	a range [L,R] is valid iff every k in [1,N] exist atleast one important point

	we can show sufficiency by noticing that 

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

	also notice that important points are two consecutive terms in (*)
	
	now plot each f(l,r) in a similar fashion to pascal's triangle 
	where each row groups all ranges with same length

	assume we reach the k-th row and want to go down to (k+1) th row
		
	if we're in the left imp. point of k-th row which is in [L,R]
	
	the option is to either go to the left imp. point of (k+1)-th row of right imp. point

	if left imp. point is in [L,R] we are done

	if left imp. point isn't in [L,R] then it must either be in [1,L) or (R,N]

	if it is in (R,N], this is absurd due to our assumption that there exist an imp point of range
	(k+1) in [L,R]
	
	if it is in [1,L), then the right imp. point must be in [L,R] so we can go there and we are done.
	
	this is because since we are in left imp. point of k-th row
	it can produce to imp. point in k+1 th row
	also notice that f(l,r-1) < f(l,r) < f(l+1,r) 
	so what it produces is one is to its left and one is to its right
	since one is already to its left, the other one must be to its right
	
	*/
	
	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(idL[k]) {
			fw.upd(idL[k],-1);
			fw.upd(idR[k],1);
			idL[k]=0;
		} else {
			fw.upd(idR[k],-1);
		}
	}

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

}

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