oj.uz

Submission #108337

# Submission time Handle Problem Language Result Execution time Memory
108337 2019-04-28T14:42:33 Z ami Krov (COCI17_krov) C++17
140 / 140
 907 ms 11712 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=1<<18;

struct node {
	int cnt;
	ll sum;
};

struct segment_tree {
	int n;
	ll 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,ll 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(ll x) {
		add(0,0,n-1,x,1);
	}
	
	void remove(ll x) {
		add(0,0,n-1,x,-1);
	}
	
	node query(int v,int l,int r,ll 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(ll x) const {
		return query(0,0,n-1,x);
	}
	
	node top() const {
		return tr[0];
	}
};

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

ll findX(int i) {
	ll l=-ll(2e9),r=ll(2e9);
	while (l<r) {
		ll m=l+(r-l)/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,ll 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,ll 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);
		
		ll x=findX(i);
		ll 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 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 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 9 ms 640 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 9 ms 640 KB Output is correct
2 Correct 13 ms 640 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1024 KB Output is correct
2 Correct 23 ms 640 KB Output is correct
3 Correct 13 ms 844 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2868 KB Output is correct
2 Correct 111 ms 1948 KB Output is correct
3 Correct 145 ms 2976 KB Output is correct
4 Correct 182 ms 3064 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 5288 KB Output is correct
2 Correct 237 ms 5368 KB Output is correct
3 Correct 245 ms 5368 KB Output is correct
4 Correct 243 ms 5748 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 5048 KB Output is correct
2 Correct 605 ms 11036 KB Output is correct
3 Correct 213 ms 3448 KB Output is correct
4 Correct 413 ms 6504 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 10488 KB Output is correct
2 Correct 655 ms 11712 KB Output is correct
3 Correct 439 ms 7256 KB Output is correct
4 Correct 712 ms 11276 KB Output is correct
5 Correct 191 ms 3192 KB Output is correct