oj.uz

Submission #108344

# Submission time Handle Problem Language Result Execution time Memory
108344 2019-04-28T15:40:04 Z ami Krov (COCI17_krov) C++17
140 / 140
 471 ms 6484 KB 
#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.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 6 ms 640 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 640 KB Output is correct
2 Correct 11 ms 668 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 640 KB Output is correct
2 Correct 12 ms 696 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 864 KB Output is correct
2 Correct 20 ms 768 KB Output is correct
3 Correct 12 ms 640 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2036 KB Output is correct
2 Correct 105 ms 1792 KB Output is correct
3 Correct 121 ms 2100 KB Output is correct
4 Correct 153 ms 2324 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 2904 KB Output is correct
2 Correct 220 ms 3260 KB Output is correct
3 Correct 117 ms 2804 KB Output is correct
4 Correct 109 ms 2840 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 3380 KB Output is correct
2 Correct 244 ms 4840 KB Output is correct
3 Correct 152 ms 2676 KB Output is correct
4 Correct 327 ms 4748 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 6484 KB Output is correct
2 Correct 333 ms 6296 KB Output is correct
3 Correct 360 ms 4820 KB Output is correct
4 Correct 471 ms 5876 KB Output is correct
5 Correct 75 ms 2040 KB Output is correct