QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22324 | #2356. Partition of Queries | jyyyyds# | WA | 5ms | 12004kb | C++20 | 949b | 2022-03-09 15:25:57 | 2022-04-30 00:54:00 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
int n,m;
char str[N];
int c[N];
ll s[N];
ll f[N];
int p[N],L[N],hd=1,tl=0;
inline ll w(int l,int r){
return f[l]+m+s[r-1]-s[l]-1ll*l*(c[r-1]-c[l]);
}
int main(){
scanf("%d%d%s",&n,&m,str+1);
int tmp=0;
for(int i=1;i<=n;i++){
if(str[i]=='+')
tmp++;
else
c[tmp]++,s[tmp]+=tmp;
}
n=tmp;
for(int i=1;i<=n;i++)
c[i]+=c[i-1],s[i]+=s[i-1];
f[0]=0,p[++tl]=0,L[tl]=1;
ll ans=w(0,n+1)-m;
for(int i=1;i<=n;i++){
if(hd<tl&&++L[hd]==L[hd+1])
hd++;
f[i]=w(p[hd],i);
ans=std::min(ans,w(i,n+1)-m);
while(hd<tl&&w(i,L[tl])<=w(p[tl],L[tl]))
tl--;
if(hd<=tl){
int l=L[tl],r=n,res=r+1;
while(l<=r){
int mid=(l+r)>>1;
if(w(i,mid)<=w(p[tl],mid))
res=mid,r=mid-1;
else
l=mid+1;
}
if(res!=n+1)
p[++tl]=i,L[tl]=res;
}
else
p[++tl]=i,L[tl]=i+1;
}
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 11976kb
input:
6 5 ++??+?
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 2ms
memory: 11888kb
input:
6 8 ++??+?
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 5ms
memory: 11912kb
input:
5 1 +++++
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 12004kb
input:
10 0 ++?+??++??
output:
6
result:
wrong answer 1st lines differ - expected: '0', found: '6'