QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22395#2356. Partition of QueriesHYLTianMeng#WA 50ms22360kbC++202.6kb2022-03-09 17:06:202022-04-30 01:01:17

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:01:17]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:22360kb
  • [2022-03-09 17:06:20]
  • 提交

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'