oj.uz

Submission #858808

# Submission time Handle Problem Language Result Execution time Memory
858808 2023-10-09T08:17:13 Z Youssif_Elkadi Krov (COCI17_krov) C++17
140 / 140
 923 ms 11680 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3SJjfN1 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
 
struct fenwick{
	int n;
	vector <int> bit;
	fenwick(int m){
		init(m);
	}
	void init(int m){
		n=m;
		bit.resize(n+1,0);
	}
	int get(int i){
		int s=0;
		while(i<=n){
			s+=bit[i];
			i+=i&-i;
		}
		return s;
	}
	void add(int i,int x){
		while(i>0){
			bit[i]+=x;
			i-=i&-i;
		}
	}
};
 
signed main(){
_3SJjfN1;
	int n;
	// n=100000;
	cin>>n;
	vi a(n);
	rep(i,n){
		// a[i]=randint((int)(1ll<<29))+1;
		cin>>a[i];
	}
	// to the left i need
	// x - pvt = y - i
 
	// to the right i need
	// x - y = i - pvt
	// x + pvt = i + y
	vi tmp;
	rep(i,n){
		tmp.pb(a[i]-i);
		tmp.pb(a[i]+i);
	}
	sort(tmp.begin(),tmp.end());
	tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	const int m=sz(tmp);
 
	vi idsl(n),idsr(n);
	rep(i,n){
			int v=a[i]-i;
			int j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
			idsl[i]=j;
			 v=a[i]+i;
			 j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
			idsr[i]=j;
	}
 
	// atcoder::segtree<int,op,e> segl(m),cntl(m),segr(m),cntr(m);
	fenwick bitl(m),cntl(m),bitr(m),cntr(m);
	int psunl=0,pcntl=0,psunr=0,pcntr=0;
 
	auto af=[&](const int&pvt,const int&x)->int{
		int res=0;
		// to the left 
		int v=x-pvt;
		// >=
		int j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
		int sun=psunl,now=pcntl;
		if(j>=0 and j<sz(tmp)){
			int vala=bitl.get(j+1);
			int valb=cntl.get(j+1);
			res+=vala-valb*v;
			sun-=vala;
			now-=valb;
		}
		// <=
		if(j>=0 and j<=sz(tmp)){
			res+=now*v-sun;
		}
		// to the right
		v=x+pvt;
		j=lower_bound(tmp.begin(),tmp.end(),v)-tmp.begin();
		sun=psunr,now=pcntr;
		if(j>=0 and j<sz(tmp)){
			int vala=bitr.get(j+1);
			int valb=cntr.get(j+1);
			res+=vala-valb*v;
			sun-=vala;
			now-=valb;
		}
		// <=
		if(j>=0 and j<=sz(tmp)){
			res+=now*v-sun;
		}
		return res;
	};
 
	rep(i,n){
		int v=a[i]+i;
		int j=idsr[i];
		psunr+=v;
		pcntr+=1;
		bitr.add(j+1,v);
		cntr.add(j+1,1);
	}
	const int inf=1e18;
	int ans=inf;
	rep(i,n){
		int l=max(i+1,n-i),r=1e9;
		while(r-l>2){
			int ml=(2*l+r)/3;
			int mr=(l+2*r)/3;
			if(af(i,ml)<af(i,mr)){
				r=mr;
			}else{
				l=ml;
			}
		}
		rng(j,l,r+1){
			ans=min(ans,af(i,j));
		}
		int v=a[i]+i;
		int j=idsr[i];
		psunr-=v;
		pcntr-=1;
		bitr.add(j+1,-v);
		cntr.add(j+1,-1);
		v=a[i]-i;
		j=idsl[i];
		psunl+=v;
		pcntl+=1;
		bitl.add(j+1,+v);
		cntl.add(j+1,+1);
	}
	print(ans);
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 344 KB Output is correct
2 Correct 6 ms 584 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Output is correct
2 Correct 6 ms 344 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 616 KB Output is correct
2 Correct 10 ms 600 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 600 KB Output is correct
2 Correct 16 ms 604 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 604 KB Output is correct
2 Correct 14 ms 604 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 856 KB Output is correct
2 Correct 33 ms 816 KB Output is correct
3 Correct 19 ms 604 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 2776 KB Output is correct
2 Correct 162 ms 2376 KB Output is correct
3 Correct 201 ms 2780 KB Output is correct
4 Correct 254 ms 3468 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 4172 KB Output is correct
2 Correct 387 ms 4768 KB Output is correct
3 Correct 289 ms 4824 KB Output is correct
4 Correct 296 ms 4632 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 5824 KB Output is correct
2 Correct 625 ms 8620 KB Output is correct
3 Correct 301 ms 3984 KB Output is correct
4 Correct 676 ms 7624 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 812 ms 11680 KB Output is correct
2 Correct 733 ms 11212 KB Output is correct
3 Correct 672 ms 7628 KB Output is correct
4 Correct 923 ms 9708 KB Output is correct
5 Correct 181 ms 3288 KB Output is correct