QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137354#2356. Partition of QueriesBoulevardDust#WA 2ms7936kbC++141.7kb2023-08-10 11:00:112023-08-10 11:00:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 11:00:12]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7936kb
  • [2023-08-10 11:00:11]
  • 提交

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;
}

详细

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'