QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22432#2356. Partition of QueriesQyc_AK_NOI2022#RE 0ms0kbC++111.5kb2022-03-09 18:12:422022-04-30 01:04:20

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:04:20]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2022-03-09 18:12:42]
  • 提交

answer

#include <cstdio>
#include <queue>
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,q[500010],d[500010];
char s[1000010];
ll dp[500010],sum[500010];
inline ll upd(int f,int t){
	return dp[f]+sum[t]-sum[f]-(ll)(d[t]-d[f])*q[t]+k;
}
inline ll mmax(ll x,ll y){return x>y?x:y;}
inline ll mmin(ll x,ll y){return x<y?x:y;}
int l[500010],r[500010];
inline int out(const int &p,const int &w){
	int hl=mmax(l[p],w+1),hr=n,mid;
	while(hl<hr){
		mid=hl+hr>>1;
		if(upd(p,mid)<=upd(w,mid))hl=mid+1;
		else hr=mid;
	}
	return hl;
}
int main(){
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	n=rd(),k=rd();
	scanf("%s",s+1);
	int at=0,pl=0;
	for(int i=1;i<=n;++i){
		if(s[i]=='+'){
			if(!pl)++at,pl=1;
			++d[at];
		}
		else{
			if(pl)pl=0;
			++q[at];
		}
	}
	n=at-pl;
	for(int i=n-1;i>0;--i)q[i]+=q[i+1];
	for(int i=1;i<=n;++i){
		sum[i]=sum[i-1]+(ll)d[i]*q[i];
		d[i]=d[i-1]+d[i];
	}
	deque<int> q;
	q.push_back(0),l[0]=1,r[0]=n;
	for(int i=1,j;i<=n;++i){
		while(r[q.front()]<i)q.pop_front();
		j=q.front();
		dp[i]=upd(j,i);
		j=q.back();
		if(upd(j,n)<=upd(i,n))continue;
		while(!q.empty()){
			j=q.back();
			if((l[i]=out(j,i))<=l[j])q.pop_back();
			else {r[j]=l[i]-1;break;}
		}
		r[i]=n,q.push_back(i);
	}
	ll ans=0x3f3f3f3f3f3f3f3f;
	for(int i=0;i<=n;++i)
		ans=mmin(ans,sum[n]-sum[i]+dp[i]);
	printf("%lld\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

6 5
++??+?

output:


result: