Submission #108344

#	Time	Username	Problem	Language	Result	Execution time	Memory
108344		ami	Krov (COCI17_krov)	C++17	140 / 140	471 ms	6484 KiB

krov

#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;

ll const INF=ll(1e18);
int const MAXN=110000;

vector<int> a;

int findPos(int x) {
	return int(upper_bound(a.begin(),a.end(),x)-a.begin()) - 1; 
}

struct fenwick {
	static const int SZ=2*MAXN;
	int cnt[SZ];
	ll sum[SZ];
	int totalCount;
	ll totalSum;
	
	void update(int pos,int d) {
		totalCount+=d;
		totalSum+=d*a[pos];
		for (int i=pos; i<SZ; i|=i+1) {
			cnt[i]+=d;
			sum[i]+=d*a[pos];
		}
	}
	
	void add(int x) {
		update(findPos(x),+1);
	}
	
	void remove(int x) {
		update(findPos(x),-1);
	}
	
	int queryCount(int x) const {
		int c=0;
		for (int i=findPos(x); i>=0; i&=i+1, i--) c+=cnt[i];
		return c;
	}
	
	ll querySum(int x) const {
		ll s=0;
		for (int i=findPos(x); i>=0; i&=i+1, i--) s+=sum[i];
		return s;
	}
};

int N;
int H[MAXN];
fenwick L,R;

int findX(int i) {
	int l=-MAXN,r=int(1e9)+MAXN;
	while (l<r) {
		int m=l+(r-l)/2;
		int cntL=L.queryCount(m-i);
		int cntR=R.queryCount(m+i);
		if (2*(cntL+cntR)<N) l=m+1; else r=m;
	}
	return l;
}

ll findSum(const fenwick &F,int x) {
	ll cnt=F.queryCount(x);
	ll sum=F.querySum(x);
	return cnt*x-sum + (F.totalSum-sum)-(F.totalCount-cnt)*x;
}

ll findSum(int i,int x) {
	return findSum(L,x-i)+findSum(R,x+i);
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>N;
	rep(i,0,N) cin>>H[i];
	
	rep(i,0,N) {
		a.push_back(H[i]-i);
		a.push_back(H[i]+i);
	}
	sort(a.begin(),a.end());
	
	rep(i,0,N) R.add(H[i]+i);
	
	ll res=INF;
	rep(i,0,N) {
		L.add(H[i]-i);
		R.remove(H[i]+i);
		
		int x=findX(i);
		int low=min(x-i,x-(N-1-i));
		if (low<=0) x+=1-low;
		
		ll sum=findSum(i,x);
		res=min(res,sum);
	}
	
	cout<<res<<"\n";
}

• 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