oj.uz

Submission #58748

# Submission time Handle Problem Language Result Execution time Memory
58748 2018-07-19T08:16:15 Z hamzqq9 Krov (COCI17_krov) C++14
126 / 140
 1500 ms 18780 KB 
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 998244353
#define inf 1000000001
#define N 100005
#define LOG 20
#define KOK 350
#define EPS 0.000000000001
#define pw(x) (1<<(x))
#define PI 3.1415926535
using namespace std;

struct SEG {

	int totok;
	int mx;
	ll sum;

} S[2][N*4],temp={0,-inf,0};

int n,x;
int lazy[2][N*4],orderL[N],orderR[N];
ii L[N],R[N];
ll ans=1ll*inf*inf;

SEG merge(SEG A,SEG B) {

	return {A.totok+B.totok,max(A.mx,B.mx),A.sum+B.sum};

}

void push(int node,int bas,int son,int w) {

	S[w][node*2].mx+=lazy[w][node];
	S[w][node*2+1].mx+=lazy[w][node];

	S[w][node*2].sum+=lazy[w][node]*S[w][node*2].totok;
	S[w][node*2+1].sum+=lazy[w][node]*S[w][node*2+1].totok;

	lazy[w][node*2]+=lazy[w][node];
	lazy[w][node*2+1]+=lazy[w][node];

	lazy[w][node]=0;

}

SEG get(int node,int bas,int son,int val,int w) {

	if(bas==son) return S[w][node].mx<=val?S[w][node]:temp;

	push(node,bas,son,w);

	if(S[w][node*2].mx<=val) return merge(S[w][node*2],get(node*2+1,orta+1,son,val,w));

	return get(node*2,bas,orta,val,w);

}

void upok(int node,int bas,int son,int x,int val,int w) {

	if(bas>x || son<x) return ;

	if(bas==x && son==x) {

		S[w][node].totok=val;

		S[w][node].sum=S[w][node].mx*val;

		return ;

	} 

	push(node,bas,son,w);

	upok(node*2,bas,orta,x,val,w);
	upok(node*2+1,orta+1,son,x,val,w);

	S[w][node]=merge(S[w][node*2],S[w][node*2+1]);

}

void up(int node,int bas,int son,int x,int y,int val,int w) {

	if(bas>y || son<x) return ;

	if(bas>=x && son<=y) {

		S[w][node].mx+=val;

		S[w][node].sum+=1ll*(S[w][node].totok)*val;

		lazy[w][node]+=val;

		return ;

	}

	push(node,bas,son,w);

	up(node*2,bas,orta,x,y,val,w);
	up(node*2+1,orta+1,son,x,y,val,w);

	S[w][node]=merge(S[w][node*2],S[w][node*2+1]);

}

ll solve(int val,int ind) {

	val=-val;

	umax(val,max(ind,n-ind+1));

	val=-val;

	SEG ALL=merge(S[0][1],S[1][1]);
	SEG SMEQ=merge(get(1,1,n,val,0),get(1,1,n,val,1));
	SEG BIG={ALL.totok-SMEQ.totok,0,ALL.sum-SMEQ.sum};

	return -(-1ll*val*SMEQ.totok+SMEQ.sum)+BIG.sum-1ll*val*BIG.totok;

}

int main() {

	#if 0

	freopen("input.txt","r",stdin);

	#endif

	scanf("%d",&n);

	for(int i=1;i<=n;i++) {

		scanf("%d",&x);

		L[i]={i-x,i};
		R[i]={-i-x,i};

	}

	sort(L+1,L+1+n);
	sort(R+1,R+1+n);

	for(int i=1;i<=n;i++) {

		orderL[L[i].nd]=i;
		orderR[R[i].nd]=i;

	}

	for(int i=1;i<=n;i++) {

		up(1,1,n,i,i,R[i].st,1);
		up(1,1,n,i,i,L[i].st,0);

		upok(1,1,n,i,1,1);
		upok(1,1,n,i,0,0);

	}

	for(int i=1;i<=n;i++) {

		up(1,1,n,1,n,1,1);
		up(1,1,n,1,n,-1,0);

		int bas=-inf,son=inf;

		while(bas<=son) {

			int totL=get(1,1,n,orta,0).totok;
			int totR=get(1,1,n,orta,1).totok;

			if(totL+totR<(n+1)/2) bas=orta+1;
			else son=orta-1;

		}

		umin(ans,solve(bas,i));

		upok(1,1,n,orderR[i],0,1);
		upok(1,1,n,orderL[i],1,0);

	}

	printf("%lld",ans);

}

Compilation message

krov.cpp: In function 'int main()':
krov.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
krov.cpp:162:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 872 KB Output is correct
2 Correct 16 ms 1004 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1008 KB Output is correct
2 Correct 21 ms 1008 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1336 KB Output is correct
2 Correct 42 ms 1336 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1336 KB Output is correct
2 Correct 32 ms 1336 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 1864 KB Output is correct
2 Correct 71 ms 1912 KB Output is correct
3 Correct 36 ms 1912 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 4476 KB Output is correct
2 Correct 438 ms 4752 KB Output is correct
3 Correct 393 ms 4916 KB Output is correct
4 Correct 504 ms 5168 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 8200 KB Output is correct
2 Correct 771 ms 8452 KB Output is correct
3 Correct 657 ms 8860 KB Output is correct
4 Correct 646 ms 9236 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1233 ms 15748 KB Output is correct
2 Correct 1427 ms 16480 KB Output is correct
3 Correct 654 ms 16480 KB Output is correct
4 Correct 1366 ms 17312 KB Output is correct

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1588 ms 18780 KB Time limit exceeded
2 Halted 0 ms 0 KB -