oj.uz

Submission #974270

# Submission time Handle Problem Language Result Execution time Memory
974270 2024-05-03T07:09:35 Z happy_node Seesaw (JOI22_seesaw) C++17
100 / 100
 169 ms 29376 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 2 ms 8944 KB Output is correct
11 Correct 3 ms 8936 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8536 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 3 ms 8796 KB Output is correct
10 Correct 2 ms 8944 KB Output is correct
11 Correct 3 ms 8936 KB Output is correct
12 Correct 164 ms 28880 KB Output is correct
13 Correct 156 ms 28100 KB Output is correct
14 Correct 161 ms 28360 KB Output is correct
15 Correct 152 ms 29376 KB Output is correct
16 Correct 169 ms 28944 KB Output is correct