oj.uz

Submission #646845

# Submission time Handle Problem Language Result Execution time Memory
646845 2022-09-30T21:33:04 Z inksamurai Krov (COCI17_krov) C++17
140 / 140
 1190 ms 11276 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;
		}
		{
			int v=a[i]+i;
			int 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 6 ms 340 KB Output is correct
2 Correct 7 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 404 KB Output is correct
2 Correct 7 ms 440 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 476 KB Output is correct
2 Correct 13 ms 468 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 468 KB Output is correct
2 Correct 22 ms 468 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 544 KB Output is correct
2 Correct 18 ms 580 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 724 KB Output is correct
2 Correct 43 ms 644 KB Output is correct
3 Correct 22 ms 604 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 2576 KB Output is correct
2 Correct 231 ms 2080 KB Output is correct
3 Correct 261 ms 2644 KB Output is correct
4 Correct 322 ms 3156 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 3796 KB Output is correct
2 Correct 509 ms 4272 KB Output is correct
3 Correct 399 ms 4304 KB Output is correct
4 Correct 399 ms 4132 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 4996 KB Output is correct
2 Correct 816 ms 8484 KB Output is correct
3 Correct 400 ms 3792 KB Output is correct
4 Correct 845 ms 7456 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 10496 KB Output is correct
2 Correct 1024 ms 11276 KB Output is correct
3 Correct 874 ms 7504 KB Output is correct
4 Correct 1190 ms 9580 KB Output is correct
5 Correct 242 ms 3172 KB Output is correct