QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22324#2356. Partition of Queriesjyyyyds#WA 5ms12004kbC++20949b2022-03-09 15:25:572022-04-30 00:54:00

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 00:54:00]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:12004kb
  • [2022-03-09 15:25:57]
  • 提交

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'