Submission #58749

#	Time	Username	Problem	Language	Result	Execution time	Memory
58749		hamzqq9	Krov (COCI17_krov)	C++14	126 / 140	1585 ms	13164 KiB

krov

#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=2*N;

		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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 0 / 14