Submission #646845

#	Time	Username	Problem	Language	Result	Execution time	Memory
646845		inksamurai	Krov (COCI17_krov)	C++17	140 / 140	1190 ms	11276 KiB

krov

#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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14