QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402831#1286. Ternary String CountingdengziyueWA 1ms4200kbC++142.3kb2024-05-01 16:07:322024-05-01 16:07:33

Judging History

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

  • [2024-05-01 16:07:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4200kb
  • [2024-05-01 16:07:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define max_n 5000
#define mod 1000000007ll
int tid;
int n;
int m;
struct L{int l1,r1,l2,r2;};
vector<L>lim[max_n+2];
long long dp[max_n+2][max_n+2];
long long sx[max_n+2];
long long sy[max_n+2];
long long ans=0;
inline void upd(int x,int y,long long w){
	dp[x][y]=(dp[x][y]+w)%mod; sx[x]=(sx[x]+w)%mod; sy[y]=(sy[y]+w)%mod;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("QOJ1286_1.in","r",stdin);
	freopen("QOJ1286_1.out","w",stdout);
	#endif
	scanf("%d",&tid);
	for(int ca=1;ca<=tid;++ca){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)lim[i].clear();
		bool ok=true;
		for(int i=1,l,r,w;i<=m;++i){
			scanf("%d%d%d",&l,&r,&w);
			if(r-l+1<w)ok=false;
			if(w==1)lim[r].push_back((L){0,l-1,0,l-1});
			if(w==2)lim[r].push_back((L){l,n,0,l-1});
			if(w==3)lim[r].push_back((L){l,n,l,n});
		}
		if(!ok){printf("0\n"); continue;}
		for(int i=0;i<=n;++i){
			for(int j=0;j<=n;++j)dp[i][j]=0;
			sx[i]=sy[i]=0;
		}
		dp[0][0]=sx[0]=sy[0]=3;
		int nowl1=0,nowr1=n,nowl2=0,nowr2=n;
		for(int i=2;i<=n&&nowl1<=nowr1&&nowl2<=nowr2;++i){
			vector<pair<pair<int,int>,long long>>op;
			for(int j=0;j<=n;++j)op.push_back({{i-1,j},sx[j]});
			for(int k=0;k<=n;++k)op.push_back({{i-1,k},sy[k]});
			for(auto u:op)upd(u.first.first,u.first.second,u.second);
			for(auto u:lim[i]){
				int tol1=max(nowl1,u.l1),tor1=min(nowr1,u.r1),tol2=max(nowl2,u.l2),tor2=min(nowr2,u.r2);
				if(tol1>tor1||tol2>tor2){nowl1=tol1; nowr1=tor1; nowl2=tol2; nowr2=tor2; break;}
				for(int j=nowl1;j<=tol1-1;++j){
					for(int k=nowl2;k<=nowr2;++k)upd(j,k,mod-dp[j][k]);
				}
				for(int j=tol1;j<=tor1;++j){
					for(int k=nowl2;k<=tol2-1;++k)upd(j,k,mod-dp[j][k]);
					for(int k=tor2+1;k<=nowr2;++k)upd(j,k,mod-dp[j][k]);
				}
				for(int j=tor1+1;j<=nowr1;++j){
					for(int k=nowl2;k<=nowr2;++k)upd(j,k,mod-dp[j][k]);
				}
				nowl1=tol1; nowr1=tor1; nowl2=tol2; nowr2=tor2;
			}
			/*printf("\n[%d,%d] [%d,%d]\n",nowl1,nowr1,nowl2,nowr2);
			for(int j=0;j<=n;++j){
				for(int k=0;k<=n;++k){
					printf("%lld ",dp[j][k]);
				}printf("\n");
			}*/ 
		}
		if(nowl1<=nowr1&&nowl2<=nowr2){
			ans=0;
			for(int i=nowl1;i<=nowr1;++i){
				for(int j=nowl2;j<=nowr2;++j)ans=(ans+dp[i][j])%mod;
			}
			printf("%lld\n",(ans%mod+mod)%mod);
		}
		else printf("0\n");
	}
	return 0;
}

详细

Test #1:

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

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: 3900kb

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:

60
0
0
0
0
0
0
0
768
0
0
30
1944
0
3024
288
0
0
0
0
0
0
0
0
0
0
0
0
0
0
96
0
0
0
0
0
0
0
0
0
24
0
0
0
2916
0
0
0
0
0
0
0
0
0
0
0
8748
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1608
0
0
36
0
0
1116
0
0
0
0
0
0
0
6
0
0
0
0
0
0
0
216
0
0
0
0
0
0
0
0
18
0
0
0
0
0
0
0
0
9
810
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st words differ - expected: '90', found: '60'