QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #816827 | #8923. За связь без перебоев | kkkgjyismine4 | 0 | 2ms | 18044kb | C++20 | 1.1kb | 2024-12-16 18:26:38 | 2024-12-16 18:26:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define ll long long
#define pb push_back
int a[N],b[N],n,x;
ll f[N];
int L[N],R[N],st[N],tl,sz[N],bl[N];
vector<int>vec[N];
bool cmp(int a,int b){return L[a]<L[b];}
ll calc(int ps){
for(int i=1;i<=n;++i)a[i]=b[i],vec[i].clear();
if(ps)a[ps]=x;tl=0;
for(int i=1;i<=n;++i){
L[i]=max(i-a[i],1),R[i]=min(i+a[i],n);
vec[R[i]].pb(i);
}
for(int i=1;i<=n;++i){
sort(vec[i].begin(),vec[i].end(),cmp);
for(int v:vec[i]){
if(tl&&R[st[tl]]>=R[v])continue;
while(tl&&L[st[tl]]>=L[v])--tl;
st[++tl]=v;
}
}
for(int i=tl;i;--i)sz[i]=0;
L[0]=R[0]=0;
for(int i=tl;i;--i)
for(int j=R[st[i]-1]+1;j<=R[st[i]];++j)bl[j]=i;
bl[n+1]=0;
ll s=0;
for(int i=1;i<=tl;++i){
sz[i]+=R[st[i]]-R[st[i-1]];
s+=1ll*sz[i]*(n-R[st[i]]);
sz[bl[R[st[i]]+1]]+=sz[i];
}return s;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>x;
for(int i=1;i<=n;++i)cin>>b[i];
ll ans=calc(0);
for(int i=1;i<=n;++i){
if(b[i]>=x)continue;
ans=min(ans,calc(i));
}cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 7
Accepted
time: 0ms
memory: 15876kb
input:
1 0 0
output:
0
result:
ok answer is '0'
Test #2:
score: 7
Accepted
time: 0ms
memory: 18044kb
input:
1 1 0
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Wrong Answer
time: 2ms
memory: 13900kb
input:
100 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
93491
result:
wrong answer expected '161651', found '93491'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Runtime Error
Test #39:
score: 0
Runtime Error
input:
1000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
result:
Subtask #5:
score: 0
Runtime Error
Test #53:
score: 0
Runtime Error
input:
1000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Runtime Error
Test #74:
score: 0
Runtime Error
input:
1000000 0 50003 50006 50006 50003 50005 50010 50006 50007 50002 50000 50005 50003 50002 50005 50000 50008 50010 50008 50007 50000 50003 50001 50008 50005 50002 50005 50006 50001 50002 50009 50006 50007 50010 50008 50000 50005 50006 50006 50003 50001 50000 50008 50000 50003 50008 50009 50006 50000 50...
output:
result:
Subtask #8:
score: 0
Skipped
Dependency #1:
0%