oj.uz

Submission #108342

# Submission time Handle Problem Language Result Execution time Memory
108342 2019-04-28T15:37:44 Z ami Krov (COCI17_krov) C++17
140 / 140
 458 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=-100000,r=1000100000;
	while (l<r) {
		int m=int(l+(ll(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 4 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 4 ms 512 KB Output is correct
2 Correct 5 ms 512 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 9 ms 640 KB Output is correct

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 896 KB Output is correct
2 Correct 20 ms 768 KB Output is correct
3 Correct 10 ms 640 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 2036 KB Output is correct
2 Correct 104 ms 1792 KB Output is correct
3 Correct 105 ms 2120 KB Output is correct
4 Correct 152 ms 2344 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 2920 KB Output is correct
2 Correct 199 ms 3084 KB Output is correct
3 Correct 133 ms 2804 KB Output is correct
4 Correct 135 ms 2804 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 3316 KB Output is correct
2 Correct 222 ms 4848 KB Output is correct
3 Correct 156 ms 2556 KB Output is correct
4 Correct 351 ms 4796 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 6484 KB Output is correct
2 Correct 316 ms 6212 KB Output is correct
3 Correct 324 ms 4720 KB Output is correct
4 Correct 458 ms 5848 KB Output is correct
5 Correct 87 ms 2040 KB Output is correct