QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#160147#5246. Nawiasowe podziały [B]HMSF0 196ms453532kbC++144.6kb2023-09-02 19:35:342023-09-02 19:35:36

Judging History

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

  • [2023-09-02 19:35:36]
  • 评测
  • 测评结果:0
  • 用时:196ms
  • 内存:453532kb
  • [2023-09-02 19:35:34]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
//#include<set>
//#include<queue>
//#include<stack>
#define PII pair<int,int>
#define MP make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
inline LL read()
{
	LL s=0; bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=1; ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
	return w ? ~s+1 : s;
}

const int maxn = 400005;
const int inf = 2147483624;
const LL infl = 9223372036854775807;

int n,m;
char str[maxn];
int a[maxn]; //前缀和

struct Node
{
	int l,r;
	vector<int> son;
	vector<int> typ;
}tr[maxn*20];
int tot;

void MakeNode(int l,int r,int fa,int x,int t)
{
	tr[x].l = l; tr[x].r = r; tr[fa].son.emplace_back(x); tr[fa].typ.emplace_back(t);
}

void Build(int l,int r,int x)
{
	if(l>=r) return;
	int minn = inf,lst = l;
	for(int i=l; i<=r; i++) minn = min(minn,a[i]);
	tr[x].son.emplace_back(0); tr[x].typ.emplace_back(0);
	for(int i=l; i<=r; i++)
	{
		if(a[i] == minn)
		{
			if(lst <= i-1)
			{
				MakeNode(lst,i-1,x,++tot,0);
				Build(lst,i-1,tot);
			}
			MakeNode(i,i,x,++tot,1);
			lst = i+1;
		}
		else if(i==r) //以防最后一个不是最小值
		{
			MakeNode(lst,i,x,++tot,0);
			Build(lst,i,tot);
		}
	}
	//printf("%d %d~%d son: ",x,tr[x].l,tr[x].r);
	//for(int i=1; i<tr[x].son.size(); i++) { printf("%d[%d] ",tr[x].son[i],tr[x].typ[i]); }
	//printf("\n");
	return;
}

struct DP1
{
	LL val; //子串的数目
	int num; //切了多少刀
	DP1(){}; DP1(LL val_,int num_) {val = val_; num = num_;}
}f[maxn],g[maxn]; //在每个节点处用于计算当前节点的f
LL h[maxn]; //每个节点不被切时的贡献
LL pre[maxn],sum[maxn];

struct DP2
{
	LL x,y;
	int num;
	DP2(){}; DP2(LL x_,LL y_,LL n_){x=x_; y=y_; num=n_;}
}que[maxn<<2];
int hd,tl;
LL tng; //切线的斜率

double Slope(DP2 x,DP2 y) { return y.x == x.x ? inf : (1.0*(y.y - x.y)/(y.x - x.x)); }

void Push(DP2 d)
{
	while(tl>hd && Slope(que[tl],d) < Slope(que[tl-1],que[tl])) {tl--;}
	que[++tl] = d; return;
}

void Pop() { while(tl>hd && Slope(que[hd],que[hd+1]) < tng) hd++; }

void DP(int u,LL K) //K是每一个段需要减去的额外价值
{
	if(tr[u].l > tr[u].r) {f[u].val = f[u].num = 0; return; } //空区间根本没法下刀
	if(tr[u].l == tr[u].r) {f[u].val = -K; f[u].num = 1; return;} //如果只有一个,只能切一刀
	int sz = tr[u].son.size()-1;
	for(int i=1; i<=sz; i++) { DP(tr[u].son[i],K); }
	for(int i=1; i<=sz; i++)
	{
		sum[i] = sum[i-1] + h[tr[u].son[i]];
		pre[i] = pre[i-1] + tr[u].typ[i];
	}
	//printf("now at node %d\n",u);
	//for(int i=1; i<=sz; i++) printf("%lld ",sum[i]);
	//printf("\n");
	//for(int i=1; i<=sz; i++) printf("%lld ",pre[i]);
	//printf("\n");
	hd = 1; tl = 0;
	Push(DP2(0,0,0));
	for(int i=1; i<=sz; i++)
	{
		tng = pre[i]; Pop();
		//printf("tangent = %d\n",tng);
		//for(int i=hd; i<=tl; i++) printf("(%d %d %d) ",que[i].x,que[i].y,que[i].num);
		//printf("\n");
		g[i].val = que[hd].y - que[hd].x * tng
		         + f[tr[u].son[i]].val + sum[i-1] + ((pre[i]-1)*pre[i])/2;
		g[i].num = que[hd].num + f[tr[u].son[i]].num;
		Push(DP2(pre[i-1],g[i].val - sum[i] + ((pre[i-1]+1)*pre[i-1])/2,g[i].num));
		//printf("g[%d] = %lld\n",i,g[i].val);
	}
	LL tmp = 0;
	LL minn = infl,res = 0;
	for(int i=sz; i>=1; i--) //这里是不是可以改成0,来避免后面的特判
	{
		g[i].val += tmp + ((pre[sz] - pre[i-1])-1)*(pre[sz] - pre[i-1])/2;
		tmp += h[tr[u].son[i]];
		if(g[i].val<minn || (g[i].val == minn && g[i].num>g[res].val))
			{ minn = g[i].val; res = i; }
	}
	h[u] = sum[sz] + ((pre[sz]-1)*pre[sz])/2;
	f[u].val = g[res].val; f[u].num = g[res].num;
	//printf("res = %lld f[u] = (%lld %d)\n",res,f[u].val,f[u].num);
	//printf("h[%d] = %lld\n",u,h[u]);
	//if(f[u].val > h[u]){f[u].val = h[u]; f[u].num = 0;}
	return;
}

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	n = read(); m = read();
	scanf("%s",str+1);
	a[1] = 0;
	for(int i=1; i<=n; i++) a[i+1] = a[i] + (str[i] == '(' ? 1 : -1);
	n++;
	tr[1].l = 1; tr[1].r = n;
	Build(1,n,++tot);
	int l = -n*n,r = 1,mid;
	LL minans = infl;
	while(l<r)
	{
		mid = (l+r)>>1;
		//printf("K=%d\n",mid);
		DP(1,mid);
		//printf("f1[].val = %d f[1].num = %d\n",f[1].val,f[1].num);
		if(f[1].val > h[1]) {f[1].val = h[1]; f[1].num = 0; }
		if(f[1].num+1 >= m) {minans = min(minans,f[1].val); r = mid;}
		else l = mid+1;
	}
	if(minans == infl) {printf("0\n"); return 0;}
	printf("%lld\n",minans + (m-1)*l);
	//fclose(stdin);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 1
Accepted
time: 51ms
memory: 446320kb

input:

1 1
(

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 53ms
memory: 448360kb

input:

1 1
)

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 61ms
memory: 448288kb

input:

2 1
()

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 54ms
memory: 448376kb

input:

2 1
)(

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 52ms
memory: 446308kb

input:

2 2
()

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 53ms
memory: 446264kb

input:

2 2
)(

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 55ms
memory: 446240kb

input:

10 4
()))(()(()

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 67ms
memory: 448352kb

input:

15 4
())))()(()()(((

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 51ms
memory: 448368kb

input:

18 18
(()()()))(())(((((

output:

0

result:

ok single line: '0'

Test #10:

score: -1
Wrong Answer
time: 61ms
memory: 446312kb

input:

18 3
(())(()()()())()()

output:

3

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #16:

score: 0
Wrong Answer
time: 59ms
memory: 448304kb

input:

300 25
((()()()(()())(((())())()))()((()(())))((()()))((()()))()()(((())())))((((())(()()()())(((()))(()())()(())())()()()()())(()((()()()))))(())()((()))((()))(()(()())))((()(())(((()))))((()()()()()())())(((()))()()()(())())(())()(((()))()((()()())))((())())(((()())())((()))(()()()()(())(()())((()...

output:

12

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #33:

score: 1
Accepted
time: 59ms
memory: 448476kb

input:

4000 1
(((((())())()((())(())(()()())()())(()(())(()))()(()))(()((())()()()()(()())(()()()))()(())()()(()(()()())))(()))(()(((()))()())((())(()()(()()))))((()((()())())((())())((()()))(())(())(()(()()))(((())())())((())()()(()))(()()()(()(())(()))()())((()))((())()(())()())))(((()(()()()()())(())())...

output:

5599

result:

ok single line: '5599'

Test #34:

score: -1
Wrong Answer
time: 68ms
memory: 448352kb

input:

4000 3
(((((((())))()()((((())(())()())()())(()(()())())))(()((())()((()()()((())()()))()))(())(()(()))()(()()()()((()(()))())()((()()()))(())(()()((())())))))(()(((((())))())((()()(((()()))())())())(())(()())(((()))())(()((()()()))(((()))())())())((())(())((())(())()(())()(((()))((())))))(((((())))...

output:

4546

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #54:

score: 0
Wrong Answer
time: 68ms
memory: 448440kb

input:

4000 2
((())(()(())))()((())()()()(())()()(())()((()))()()((()()))((())())((())())(()())()(())(()(()))((()())())(()())((()()))(()()())((()))()())(()(()))((()()())(())()((())()))(())((())((())))(((()(())))()(())())(()(())(())())((())(())())((()(()))()()()()(()())())(((()))(())())((()())())((())()((()...

output:

13456

result:

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

Subtask #5:

score: 0
Wrong Answer

Test #75:

score: 0
Wrong Answer
time: 144ms
memory: 451504kb

input:

100000 3
(()((())(()))(())((()())))(((()()))(()))(()()()((())))()()((())(())((())(()(()))())((())))()()((())(()()))(((())))((())()(()())(()())()(()(()()())))(()(()()))()(()((())()()()()())((()))(())(())())(((()))()(()()())()(()()))((()()))(((()()()()))(()))(((())))(((()))(()()())(()(()()))(())(()())...

output:

2874833

result:

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

Subtask #6:

score: 0
Wrong Answer

Test #89:

score: 0
Wrong Answer
time: 196ms
memory: 453464kb

input:

100000 6
((((()()((())))()((()())()())((())()(((()()))())((())((()()()))()()()(())))(((()(())(()()))(())())(())))(((()))((((())))()))(()((())(())(())((()())))(()(()(()))(())(()()()(())())(()(())(()(()))(()())()((()))()()))(()()(())))((()())()((())((())()()(((()))(())))((())())()((()())(()))))()(((()...

output:

125650

result:

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

Subtask #7:

score: 0
Wrong Answer

Test #103:

score: 0
Wrong Answer
time: 150ms
memory: 452840kb

input:

80000 81
((((((()())((()((()))))(()())()(()(((()(()())(()())())(())))()(())(()()))()))(((()(()))((()))(())((((())))(())()((()))())((()(()())))(())(()()))(((()()))(()((())))())()(((()()))(()())()()(((()((()))(())))((())(()((())))())(()())))()()()((()()(()()(())()()((()))(())()))((()(())()()))(()(()()...

output:

85956

result:

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

Subtask #8:

score: 0
Wrong Answer

Test #129:

score: 0
Wrong Answer
time: 127ms
memory: 452752kb

input:

79856 243
(())()(())(())(()()())()(())()(()())()(())()(())()((()))(())(()(())())()(()())()()(())(())((()()))(())(()()())(()())((()())()())(())()()(())()(())((()()))()()(()()())(())()()(()())(())(())((()))(())(())()()()()()(()(()))(()(())()(()))()()()()()()()()((()()))()()()()()(())()(())(()())()(()(...

output:

467404

result:

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

Subtask #9:

score: 0
Wrong Answer

Test #155:

score: 0
Wrong Answer
time: 147ms
memory: 453476kb

input:

99599 64
((((((()(((())()))))((((((()))()())())())(()(()(()())))(()(()()(())())((()(()()))((()))()(())()())()(()(())()((()()())()())()(((())()))(()))((())(()(())()))(()))())()(((())(((())()((())))())(()()(()))(()())()((())((()())()(())())(())()(())((())(()()(()))((()))(()()())))()(((()))(())))(())((...

output:

109244

result:

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

Subtask #10:

score: 0
Wrong Answer

Test #181:

score: 0
Wrong Answer
time: 167ms
memory: 453532kb

input:

100000 256
((((())()(())())(((()))()((())()(()(())))))(((()(()))(((()))()()()()))()((((()))(())((()))))((()))(()((()()()()())()())(())(())()()(()()))(((()()))))())((((()))()((())()(()(())((()))))()((()()()()((()))))()(()(()()(()(())(()))))(())(((())))((()()((()))()())()())()((()())))()(((((()()))))(...

output:

102854

result:

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