oj.uz

Submission #108336

# Submission time Handle Problem Language Result Execution time Memory
108336 2019-04-28T14:37:17 Z ami Krov (COCI17_krov) C++17
70 / 140
 818 ms 10888 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;
	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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 5 ms 384 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 384 KB Output is correct

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

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

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 2896 KB Output is correct
2 Correct 102 ms 1924 KB Output is correct
3 Correct 126 ms 3064 KB Output is correct
4 Correct 189 ms 3260 KB Output is correct

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 5340 KB Output is correct
2 Correct 269 ms 5344 KB Output is correct
3 Incorrect 262 ms 5492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 473 ms 4980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 818 ms 10888 KB Output isn't correct
2 Halted 0 ms 0 KB -