QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22395 | #2356. Partition of Queries | HYLTianMeng# | WA | 50ms | 22360kb | C++20 | 2.6kb | 2022-03-09 17:06:20 | 2022-04-30 01:01:17 |
Judging History
answer
#include<bits/stdc++.h>
#define mset(a,b) memset((a),(b),sizeof((a)))
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define dec(i,l,r) for(int i=(r);i>=(l);i--)
#define inc(a,b) (((a)+(b))>=mod?(a)+(b)-mod:(a)+(b))
#define sub(a,b) (((a)-(b))<0?(a)-(b)+mod:(a)-(b))
#define mul(a,b) 1ll*(a)*(b)%mod
#define sgn(a) (((a)&1)?(mod-1):1)
#define cmax(a,b) (((a)<(b))?(a=b):(a))
#define cmin(a,b) (((a)>(b))?(a=b):(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define N 1000010
#define M number
using namespace std;
typedef double dd;
typedef long double ld;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
//#define int long long
typedef pair<int,int> P;
typedef vector<int> vi;
const int INF=0x3f3f3f3f;
const dd eps=1e-9;
template<typename T> inline void read(T &x) {
x=0; int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
x*=f;
}
int f[N],n,sum[N],cnt[N],d[N],yy;
char s[N];
int q[N],l,r;
inline int x(int id){
return d[id];
}
inline int y(int id){
return f[id]-sum[id]+cnt[id]*d[id];
}
inline dd k(int a,int b){
if(fabs(x(a)-x(b))<=eps){
return INF;
}
return (dd)(y(a)-y(b))/(dd)(x(a)-x(b));
}
int main(){
// freopen("my.in","r",stdin);
// freopen("my.out","w",stdout);
read(n);read(yy);
scanf("%s",s+1);
int c=0;
rep(i,1,n){
if(s[i]=='+') c++;
if(s[i]=='?') sum[i]=c;
}
rep(i,1,n) sum[i]+=sum[i-1];
rep(i,1,n){
if(s[i]=='?') cnt[i]++;
}
rep(i,1,n) cnt[i]+=cnt[i-1];
rep(i,1,n) if(s[i]=='+') d[i]++;
rep(i,1,n) d[i]+=d[i-1];
// rep(i,0,n){
// printf("cnt[%d]=%d d[%d]=%d sum[%d]=%d\n",i,cnt[i],i,d[i],i,sum[i]);
// }
l=1;r=0;
f[0]=0;q[++r]=0;
rep(i,1,n){
// printf("i=%d\n",i);
// printf("r=%d\n",r);
// printf("nowk=%lf\n",k(q[l],q[l+1]));
while(r-l+1>=2&&k(q[l],q[l+1])<=(cnt[i])){
l++;
// printf("nowk=%lf\n",k(q[l],q[l+1]));
}
int now=q[l];
// printf("now=%d\n",now);
f[i]=f[now]+(sum[i]-sum[now])-(cnt[i]-cnt[now])*d[now]+yy;
while(r-l+1>=2&&k(q[r],i)<k(q[r-1],q[r])) r--;
q[++r]=i;
// printf("%d\n",q[r]);
// puts("");
}
// rep(i,1,n) printf("f[%d]=%d\n",i,f[i]);puts("");
// rep(i,1,n){
// f[i]=INF;
// rep(j,0,i-1) f[i]=min(f[i],f[j]+sum[i]-sum[j]-(cnt[i]-cnt[j])*d[j]+yy);
// }
printf("%d\n",f[n]-yy);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3744kb
input:
6 5 ++??+?
output:
6
result:
ok single line: '6'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
6 8 ++??+?
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3744kb
input:
5 1 +++++
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 3ms
memory: 3832kb
input:
10 0 ++?+??++??
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3816kb
input:
12 100 +?+++??+??++
output:
19
result:
ok single line: '19'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3784kb
input:
1 1 ?
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
9 7 ++++++++?
output:
7
result:
ok single line: '7'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
9 8 ++++++++?
output:
8
result:
ok single line: '8'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
10 15 ++++++++??
output:
15
result:
ok single line: '15'
Test #10:
score: 0
Accepted
time: 3ms
memory: 3784kb
input:
5 3 +?+?+
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
10 5 +?+?+??+??
output:
10
result:
ok single line: '10'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
10 7 +?+?+??+??
output:
12
result:
ok single line: '12'
Test #13:
score: 0
Accepted
time: 3ms
memory: 3756kb
input:
15 4 +?+?+??+??+??+?
output:
14
result:
ok single line: '14'
Test #14:
score: 0
Accepted
time: 4ms
memory: 3788kb
input:
15 6 +?+?+??+??+??+?
output:
18
result:
ok single line: '18'
Test #15:
score: 0
Accepted
time: 4ms
memory: 3808kb
input:
19 8 +?+?+??+??+??+?++??
output:
28
result:
ok single line: '28'
Test #16:
score: 0
Accepted
time: 3ms
memory: 3712kb
input:
20 9 +?+?+??+??+??+?++???
output:
30
result:
ok single line: '30'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
500 100 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++++...
output:
2710
result:
ok single line: '2710'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3980kb
input:
10000 100 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++...
output:
56616
result:
ok single line: '56616'
Test #19:
score: 0
Accepted
time: 8ms
memory: 12156kb
input:
500000 3000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????...
output:
17820759
result:
ok single line: '17820759'
Test #20:
score: 0
Accepted
time: 50ms
memory: 20400kb
input:
1000000 3000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++????...
output:
35626062
result:
ok single line: '35626062'
Test #21:
score: 0
Accepted
time: 31ms
memory: 20604kb
input:
1000000 1000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++????...
output:
19934461
result:
ok single line: '19934461'
Test #22:
score: 0
Accepted
time: 43ms
memory: 20480kb
input:
1000000 10000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++???...
output:
66661466
result:
ok single line: '66661466'
Test #23:
score: 0
Accepted
time: 37ms
memory: 20380kb
input:
1000000 30000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++???...
output:
117384143
result:
ok single line: '117384143'
Test #24:
score: 0
Accepted
time: 39ms
memory: 20364kb
input:
1000000 500000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++??...
output:
490361116
result:
ok single line: '490361116'
Test #25:
score: 0
Accepted
time: 40ms
memory: 20404kb
input:
1000000 1000000 +?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?...
output:
695515718
result:
ok single line: '695515718'
Test #26:
score: 0
Accepted
time: 17ms
memory: 22360kb
input:
1000000 924 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
output:
924
result:
ok single line: '924'
Test #27:
score: 0
Accepted
time: 19ms
memory: 22328kb
input:
1000000 69971 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
output:
69971
result:
ok single line: '69971'
Test #28:
score: 0
Accepted
time: 10ms
memory: 22296kb
input:
1000000 275229 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
output:
275229
result:
ok single line: '275229'
Test #29:
score: 0
Accepted
time: 9ms
memory: 22204kb
input:
1000000 275886 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
output:
275886
result:
ok single line: '275886'
Test #30:
score: -100
Wrong Answer
time: 24ms
memory: 20408kb
input:
1000000 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++...
output:
4675
result:
wrong answer 1st lines differ - expected: '2750', found: '4675'