QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22388#2356. Partition of QueriesQyc_AK_NOI2022#WA 1ms1820kbC++111.6kb2022-03-09 17:00:242022-04-30 00:59:46

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:59:46]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:1820kb
  • [2022-03-09 17:00:24]
  • 提交

answer

#include <cstdio>
using namespace std;
typedef long long ll;
inline int rd(){
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x;
}
int n,k,val[1000010];
char s[1000010];
ll dp[1000010],sum[1000010];
inline int mmax(int x,int y){return x>y?x:y;}
inline ll mmin(int x,int y){return x<y?x:y;}
inline ll price(int l,int r){
	return sum[r]-sum[l-1]-(ll)(r-l+1)*val[r+1];
}
inline ll upd(int from,int to){
	return dp[from-1]+k+price(from+1,to);
}
struct stk{
	int sl[1000010],sr[1000010],p[1000010],at;
	inline void init(){p[at=1]=1,sl[1]=1,sr[1]=n;}
	inline void push(const int x){
		int lx=0;
		while(at && sr[at]>x){
			int u=p[at];
			if(upd(x,sr[at])>=upd(u,sr[at]))break;
			int l=mmax(sl[at],x+1),r=sr[at],mid;
			if(upd(x,l)<upd(u,l)){
				lx=l,--at;
				continue;
			}
			while(l<r){
				mid=l+r+1>>1;
				if(upd(u,mid)>upd(x,mid))
					l=mid;
				else r=mid-1;
			}
			lx=l;
			break;
		}
		if(lx)p[++at]=x,sl[at]=lx,sr[at]=n;
	}
	inline void proc(const int x){
		int l=1,r=at,mid;
		while(l<r){
			mid=l+r>>1;
			if(sr[mid]<x)l=mid+1;
			else r=mid;
		}
		dp[x]=mmin(upd(p[l],x),price(1,x));
	}
}ss;
int main(){
	n=rd(),k=rd();
	scanf("%s",s+1);
	int at=0;
	for(int i=1;i<=n;++i)
		if(s[i]=='+')++at;
		else ++val[at];
	n=at;
	dp[1]=val[1];
	for(int i=n-1;i;--i)
		val[i]+=val[i+1];
	for(int i=1;i<=n;++i)
		sum[i]=sum[i-1]+val[i];
	ss.init();
	for(int i=2;i<=n;++i)
		ss.proc(i),ss.push(i);
	printf("%lld\n",mmin(dp[n],dp[n-1]+k));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 1772kb

input:

6 5
++??+?

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 1ms
memory: 1812kb

input:

6 8
++??+?

output:

7

result:

ok single line: '7'

Test #3:

score: 0
Accepted
time: 1ms
memory: 1784kb

input:

5 1
+++++

output:

0

result:

ok single line: '0'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 1820kb

input:

10 0
++?+??++??

output:

1

result:

wrong answer 1st lines differ - expected: '0', found: '1'