Submission #108336

#	Time	Username	Problem	Language	Result	Execution time	Memory
108336		ami	Krov (COCI17_krov)	C++17	70 / 140	818 ms	10888 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=1<<18;

struct node {
	int cnt;
	ll sum;
};

struct segment_tree {
	int n;
	int a[MAXN];
	node tr[MAXN];
	
	void prep(int N) {
		sort(a,a+N);
		n=int(unique(a,a+N)-a);
	}
	
	void add(int v,int l,int r,int x,int d) {	
//~ cerr<<"add "<<v<<" "<<l<<" "<<r<<" "<<i<<endl;

		if (a[l]>x || a[r]<x) return;

		if (l==r && a[l]==x) {
			tr[v].cnt+=d;
			tr[v].sum+=d*x;
			return;
		}
		
		int m=(l+r)/2;
		add(2*v+1,l,m,x,d);
		add(2*v+2,m+1,r,x,d);
		tr[v].cnt=tr[2*v+1].cnt+tr[2*v+2].cnt;
		tr[v].sum=tr[2*v+1].sum+tr[2*v+2].sum;
	}
	
	void add(int x) {
		add(0,0,n-1,x,1);
	}
	
	void remove(int x) {
		add(0,0,n-1,x,-1);
	}
	
	node query(int v,int l,int r,int x) const {
//~ cerr<<"query "<<v<<" "<<l<<" "<<r<<" "<<x<<endl;

		if (a[l]>x) return {0,0};
		if (a[r]<=x) return tr[v];
		
		int m=(l+r)/2;
		node r1=query(2*v+1,l,m,x);
		node r2=query(2*v+2,m+1,r,x);
		r1.cnt+=r2.cnt;
		r1.sum+=r2.sum;
		return r1;
	}
	
	node query(int x) const {
		return query(0,0,n-1,x);
	}
	
	node top() const {
		return tr[0];
	}
};

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

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

ll findSum(const segment_tree &T,int x) {
	node r=T.query(x);
	ll res1=r.cnt*x-r.sum;
	ll res2=(T.top().sum-r.sum) - (T.top().cnt-r.cnt)*x;
	ll res=res1+res2;
	return res;
}

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

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) {
		L.a[i]=H[i]-i;
		R.a[i]=H[i]+i;
	}

	L.prep(N);
	R.prep(N);
	
	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: 0 / 14
• Subtask 5: 14 / 14
• Subtask 6: 0 / 14
• Subtask 7: 14 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14