QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22420#2356. Partition of QueriesQyc_AK_NOI2022#TL 2ms2008kbC++111.6kb2022-03-09 17:44:552022-04-30 01:02:57

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:02:57]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:2008kb
  • [2022-03-09 17:44:55]
  • 提交

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,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;}
struct stk{
	int sl[500010],sr[500010],p[500010],at;
	inline void init(){at=1,sl[1]=1,sr[1]=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]=upd(p[l],x);
	}
	inline void push(const int x){
		int lx=0;
		while(sr[at]>x){
			int u=p[at];
			if(upd(x,sr[at])>=upd(u,sr[at]))break;
			int l=mmax(x+1,sl[at]),r=sr[at],mid;
			if(upd(x,l)>upd(u,l)){--at,lx=l;continue;}
			while(l<r){
				mid=l+r>>1;
				if(upd(x,mid)<upd(u,mid))r=mid;
				else l=mid+1;
			}
			lx=l;break;
		}
		if(lx)p[++at]=x,sl[at]=lx,sr[at]=n;
	}
}ss;
int main(){
	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];
	}
	for(int i=1;i<=n;++i){
		dp[i]=0x3f3f3f3f3f3f3f3f;
		for(int j=0;j<i;++j)
			dp[i]=mmin(dp[i],upd(j,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: 100
Accepted
time: 1ms
memory: 1824kb

input:

6 5
++??+?

output:

6

result:

ok single line: '6'

Test #2:

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

input:

6 8
++??+?

output:

7

result:

ok single line: '7'

Test #3:

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

input:

5 1
+++++

output:

0

result:

ok single line: '0'

Test #4:

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

input:

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

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 1828kb

input:

12 100
+?+++??+??++

output:

19

result:

ok single line: '19'

Test #6:

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

input:

1 1
?

output:

0

result:

ok single line: '0'

Test #7:

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

input:

9 7
++++++++?

output:

7

result:

ok single line: '7'

Test #8:

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

input:

9 8
++++++++?

output:

8

result:

ok single line: '8'

Test #9:

score: 0
Accepted
time: 0ms
memory: 1964kb

input:

10 15
++++++++??

output:

15

result:

ok single line: '15'

Test #10:

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

input:

5 3
+?+?+

output:

3

result:

ok single line: '3'

Test #11:

score: 0
Accepted
time: 0ms
memory: 1772kb

input:

10 5
+?+?+??+??

output:

10

result:

ok single line: '10'

Test #12:

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

input:

10 7
+?+?+??+??

output:

12

result:

ok single line: '12'

Test #13:

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

input:

15 4
+?+?+??+??+??+?

output:

14

result:

ok single line: '14'

Test #14:

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

input:

15 6
+?+?+??+??+??+?

output:

18

result:

ok single line: '18'

Test #15:

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

input:

19 8
+?+?+??+??+??+?++??

output:

28

result:

ok single line: '28'

Test #16:

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

input:

20 9
+?+?+??+??+??+?++???

output:

30

result:

ok single line: '30'

Test #17:

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

input:

500 100
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++++...

output:

2710

result:

ok single line: '2710'

Test #18:

score: 0
Accepted
time: 2ms
memory: 1824kb

input:

10000 100
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????++...

output:

56616

result:

ok single line: '56616'

Test #19:

score: -100
Time Limit Exceeded

input:

500000 3000
+?+?+??+??+??+?++?????++??+?+????????????+++?+?+???++?+?+++++++????++??+??+++??++++?++??+??+??+?????++++???+??++?+?++?++???++++???????+??????????++?+??+?+++???+?+???++?++?++++???++?++?????+??????+?++???++??+?++?+??+??++??++??++?+?+?+++??+??++????+?++?++?++??+?+++?+?+???+?+++?++?++++?????...

output:


result: