| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 58750 |
2018-07-19T08:35:32 Z |
hamzqq9 |
Krov (COCI17_krov) |
C++14 |
|
1500 ms |
14332 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=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;
break ;
}
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);
~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
376 KB |
Output is correct |
| 2 |
Correct |
13 ms |
612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
688 KB |
Output is correct |
| 2 |
Correct |
14 ms |
752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
752 KB |
Output is correct |
| 2 |
Correct |
21 ms |
908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
1004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
1008 KB |
Output is correct |
| 2 |
Correct |
30 ms |
1008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
1388 KB |
Output is correct |
| 2 |
Correct |
70 ms |
1388 KB |
Output is correct |
| 3 |
Correct |
28 ms |
1388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
438 ms |
3820 KB |
Output is correct |
| 2 |
Correct |
549 ms |
3852 KB |
Output is correct |
| 3 |
Incorrect |
409 ms |
3852 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
680 ms |
6652 KB |
Output is correct |
| 2 |
Correct |
686 ms |
6836 KB |
Output is correct |
| 3 |
Correct |
446 ms |
6836 KB |
Output is correct |
| 4 |
Incorrect |
548 ms |
6836 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1319 ms |
12612 KB |
Output is correct |
| 2 |
Incorrect |
1114 ms |
12684 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1275 ms |
13252 KB |
Output is correct |
| 2 |
Execution timed out |
1593 ms |
14332 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
