QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402901#1286. Ternary String CountingDiuWA 1ms6004kbC++141.5kb2024-05-01 17:23:482024-05-01 17:23:49

Judging History

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

  • [2024-05-01 17:23:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6004kb
  • [2024-05-01 17:23:48]
  • 提交

answer

// 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5010,mod=1e9+7;
int T,n,m,l1[N],r1[N],l2[N],r2[N];
ll sl[N],sr[N],f[N][N];
int cx[N],cy[N];
void clr_f(int i,int k){
	while(cx[i]<=k&&cx[i]<=cy[i]){
		sl[i]=(sl[i]-f[i][cx[i]]+mod)%mod;
		sr[cx[i]]=(sr[cx[i]]-f[i][cx[i]]+mod)%mod;
		f[i][cx[i]]=0;
		++cx[i];
	}
}
void clr_b(int i,int k){
	while(cy[i]>=k&&cx[i]<=cy[i]){
		sl[i]=(sl[i]-f[i][cy[i]]+mod)%mod;
		sr[cy[i]]=(sr[cy[i]]-f[i][cy[i]]+mod)%mod;
		f[i][cy[i]]=0;
		--cy[i];
	}
}
signed main(){
	scanf("%d",&T);
	for(;T--;){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			sl[i]=sr[i]=0;
			cx[i]=l1[i]=l2[i]=0;
			cy[i]=i,r1[i]=r2[i]=i-1;
		}
		for(int i=1,l,r,x;i<=m;i++){
			scanf("%d%d%d",&l,&r,&x);
			if(x==1){
				r1[r]=min(r1[r],l-1);
			}else if(x==2){
				l1[r]=max(l1[r],l);
				r2[r]=min(r2[r],l-1);
			}else{
				l2[r]=max(l2[r],l);
			}
		}
		f[0][0]=3;
		sl[0]=sr[0]=3;
		for(int i=2;i<=n;i++){
			for(int j=0;j+1<i;j++){
				f[i-1][j]=(sl[j]+sr[j])%mod;
				sl[i-1]=(sl[i-1]+f[i-1][j])%mod;
				sr[j]=(sr[j]+f[i-1][j])%mod;
			}
			for(int j=0;j<l1[i];j++)clr_f(j,j);
			for(int j=l1[i];j<=r1[i];j++)clr_f(j,l2[i]-1),clr_b(j,r2[i]+1);
			for(int j=r1[i]+1;j<i;j++)clr_f(j,j);
//			printf("work:%d\n",i);
//			printf("%d %d %d %d\n",l1[i],r1[i],l2[i],r2[i]);
//			for(int j=0;j<i;j++){
//				for(int k=0;k<=j;k++)if(f[j][k])printf("%d %d %d\n",j,k,f[j][k]);
//			}
		}
		int ans=0;
		for(int i=0;i<n;i++)ans=(ans+sl[i])%mod;
		printf("%d\n",ans);
	}
}

详细

Test #1:

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

input:

4
1 0
2 0
3 0
5 2
1 3 3
4 5 1

output:

3
9
27
18

result:

ok 4 tokens

Test #2:

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

input:

741
5 3
1 5 3
3 4 2
1 4 3
4 3
2 4 2
1 4 1
2 3 3
10 3
9 10 2
3 6 3
1 9 1
3 4
2 3 2
1 3 2
2 3 3
1 3 3
10 4
6 6 1
9 10 2
4 8 3
4 10 3
6 3
1 4 3
2 4 2
2 2 2
4 3
1 4 1
1 1 2
2 3 1
5 3
4 5 2
4 5 1
1 4 3
9 3
2 3 2
1 9 2
2 4 2
4 3
1 3 3
2 3 2
1 2 3
8 4
5 8 1
4 8 1
3 5 3
1 3 3
9 3
4 5 1
1 5 3
3 8 2
8 3
5 7 2...

output:

90
3
9
3
24309
27
3
3
1149
9
3
1107
2925
9
6579
927
3
3
21
3
3
3
3
3
9
9
3
3
27
3
147
9
9
9
3
9
4383
27
9
567
189
3
27
3
3033
3
3
9
9
3
3
3
3
3
189
345
9207
3
3
3
9
3
513
4329
3
3
9
27
21
3
3
21
81
3
3
27
3
3
3
2109
27
27
453
9
189
1845
3
3
3
3
3
57
9
27
3
3
3
165
1305
27
1899
351
729
3
45
45
3
9
69...

result:

wrong answer 2nd words differ - expected: '0', found: '3'