QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#137354 | #2356. Partition of Queries | BoulevardDust# | WA | 2ms | 7936kb | C++14 | 1.7kb | 2023-08-10 11:00:11 | 2023-08-10 11:00:12 |
Judging History
answer
#include<bits/stdc++.h>
#define N 1000005
#define re
#define ll long long
using namespace std;
int n,m,K,q,T;
inline void Rd(int &res){
re char c;res=0;
while(c=getchar(),c<48);
do res=(res<<3)+(res<<1)+(c^48);
while(c=getchar(),c>47);
}
int Y;
ll f[N];
ll sum1[N],sum2[N],sum0[N];
struct node{
ll k,b;
ll calc(ll x){return k*x+b;}
}V[N<<2];
bool mk[N<<2];
void update(int l,int r,node res,int p){
if(!mk[p]){
mk[p]=1;V[p]=res;
return;
}
if(l==r){
if(V[p].calc(l)<res.calc(l))V[p]=res;
return;
}
int mid=(l+r)>>1;
if(V[p].k>res.k){
if(V[p].calc(mid)<res.calc(mid)){
update(mid+1,r,V[p],p<<1|1);
V[p]=res;
}
else update(l,mid,res,p<<1);
}
else{
if(V[p].calc(mid)<res.calc(mid)){
update(l,mid,V[p],p<<1);
V[p]=res;
}
else update(mid+1,r,V[p],p<<1|1);
}
}
ll query(int l,int r,int x,int p){
if(!mk[p])return -1e18;
if(l==r)return V[p].calc(x);
int mid=(l+r)>>1;
if(x<=mid)return max(V[p].calc(x),query(l,mid,x,p<<1));
else return max(V[p].calc(x),query(mid+1,r,x,p<<1|1));
}
char c[N];
int main(){
Rd(n);Rd(Y);
scanf("%s",c+1);
for(re int i=1;i<=n;i++){
sum0[i]=sum0[i-1],sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];
if(c[i]=='+')sum1[i]++;
else sum2[i]++,sum0[i]+=sum1[i];
}
int i=0;
f[0]=0;
ll k=-sum1[i];
ll b=f[i]-sum0[i]+sum2[i]*sum1[i];
k=-k,b=-b;
node now=(node){k,b};
update(0,n,now,1);
for(re int i=1;i<=n;i++){
ll x=sum2[i];
ll res=-query(0,n,x,1);
f[i]=res+sum0[i]+Y;
ll k=-sum1[i];
ll b=f[i]-sum0[i]+sum2[i]*sum1[i];
k=-k,b=-b;
node now=(node){k,b};
update(0,n,now,1);
}
printf("%lld\n",f[n]-Y);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7764kb
input:
6 5 ++??+?
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 2ms
memory: 7712kb
input:
6 8 ++??+?
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 2ms
memory: 7848kb
input:
5 1 +++++
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 7756kb
input:
10 0 ++?+??++??
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7772kb
input:
12 100 +?+++??+??++
output:
19
result:
ok single line: '19'
Test #6:
score: 0
Accepted
time: 2ms
memory: 7756kb
input:
1 1 ?
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7780kb
input:
9 7 ++++++++?
output:
7
result:
ok single line: '7'
Test #8:
score: 0
Accepted
time: 2ms
memory: 7936kb
input:
9 8 ++++++++?
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7844kb
input:
10 15 ++++++++??
output:
15
result:
ok single line: '15'
Test #10:
score: 0
Accepted
time: 2ms
memory: 7776kb
input:
5 3 +?+?+
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 2ms
memory: 7844kb
input:
10 5 +?+?+??+??
output:
10
result:
ok single line: '10'
Test #12:
score: 0
Accepted
time: 1ms
memory: 7772kb
input:
10 7 +?+?+??+??
output:
12
result:
ok single line: '12'
Test #13:
score: -100
Wrong Answer
time: 2ms
memory: 7864kb
input:
15 4 +?+?+??+??+??+?
output:
16
result:
wrong answer 1st lines differ - expected: '14', found: '16'