QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693254#1286. Ternary String CountingcwfxlhML 85ms161624kbC++141.8kb2024-10-31 15:48:562024-10-31 15:49:27

Judging History

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

  • [2024-10-31 15:49:27]
  • 评测
  • 测评结果:ML
  • 用时:85ms
  • 内存:161624kb
  • [2024-10-31 15:48:56]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
int sakuzyo,n,m,mnlmt[5003][4],mxlmt[5003][4],k1,k2,k3,k4,k5,k6,k7,k8,k9;
ll ans,vv[5003]; 
struct dpv{
	int nxth;
	int nxtw;
	ll val;
}dp[5003][5003];
ll sumh[5003],sumw[5003];
int headh[5003],headw[5003];
void setval(int X,int Y,ll v){
	dp[X][Y].val=v;
	sumh[X]=(sumh[X]+v)%MOD;
	sumw[Y]=(sumw[Y]+v)%MOD;
	dp[X][Y].nxth=headh[X];
	dp[X][Y].nxtw=headw[Y];
	headh[X]=Y;
	headw[Y]=X;
	return;
}
void clnh(int X){
	for(int i=headh[X];i!=-1;i=dp[X][i].nxth){
		sumw[i]=(sumw[i]-dp[X][i].val)%MOD;
		dp[X][i].val=0;
	}
	headh[X]=-1;
	sumh[X]=0;
	return;
}
void clnw(int X){
	for(int i=headw[X];i!=-1;i=dp[i][X].nxtw){
		sumh[i]=(sumh[i]-dp[i][X].val)%MOD;
		dp[i][X].val=0;
	}
	headw[X]=-1;
	sumw[X]=0;
	return;
}
void getlmt(int X){
	for(int i=X-1;i>=mnlmt[X][1];i--)clnh(i);
	for(int i=0;i<mxlmt[X][2];i++)clnh(i);
	for(int i=X-1;i>=mnlmt[X][2];i--)clnw(i);
	for(int i=0;i<mxlmt[X][3];i++)clnw(i);
	return;
}
void sol(){
	cin>>n>>m;
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<4;j++){
			mnlmt[i][j]=n+1;
			mxlmt[i][j]=0;
		}
	}
	for(int i=1;i<=m;i++){
		cin>>k1>>k2>>k3;
		mnlmt[k2][k3]=min(mnlmt[k2][k3],k1);
		mxlmt[k2][k3]=max(mxlmt[k2][k3],k1);
	}
	for(int i=0;i<=n;i++){
		sumh[i]=sumw[i]=0;
		headh[i]=headw[i]=-1;
		for(int j=0;j<=n;j++){
			dp[i][j].nxth=dp[i][j].nxtw=-1;
			dp[i][j].val=0;
		}
	}
	setval(0,0,3);
	getlmt(1);
	for(int i=2;i<=n;i++){
		for(int j=0;j<i-1;j++)vv[j]=(sumh[j]+sumw[j])%MOD;
		for(int j=0;j<i-1;j++)setval(i-1,j,vv[j]);
		getlmt(i);
	}
	ans=0;
	for(int i=0;i<=n;i++)ans=(ans+sumh[i])%MOD;
	ans%=MOD;
	ans+=MOD;
	ans%=MOD;
	cout<<ans<<'\n';
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>sakuzyo;
	while(sakuzyo--)sol();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3768kb

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: 0
Accepted
time: 2ms
memory: 3708kb

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
0
0
0
24300
0
0
0
768
0
0
972
2916
0
6480
864
0
0
0
0
0
0
0
0
6
0
0
0
0
0
96
0
6
0
0
0
0
0
0
0
108
0
0
0
2916
0
0
0
0
0
0
0
0
0
0
324
8748
0
0
0
0
0
0
4320
0
0
0
18
0
0
0
0
0
0
0
0
0
0
0
1992
0
0
450
0
162
1656
0
0
0
0
0
54
0
18
0
0
0
0
744
0
1620
324
0
0
36
36
0
0
60
6
54
0
0
0
0
0
0
0
0
243
810...

result:

ok 741 tokens

Test #3:

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

input:

332
17 5
4 9 1
4 6 1
7 17 1
5 5 1
5 6 3
13 5
10 12 3
8 13 2
1 10 3
2 9 1
9 10 1
19 5
11 13 1
9 17 2
1 7 1
4 4 2
3 9 1
15 4
8 11 2
9 14 3
10 12 2
4 5 2
12 4
3 9 2
7 8 1
1 7 3
6 7 3
16 5
4 14 3
1 5 1
2 10 1
2 12 3
6 9 3
20 4
10 17 3
4 20 3
17 19 3
8 17 1
20 5
11 11 1
9 13 1
1 5 3
17 17 3
3 18 3
17 5
1...

output:

0
0
0
2047032
0
0
0
0
0
839808
0
0
0
0
0
0
0
0
0
0
0
0
44641044
0
20412
0
0
0
0
0
0
0
6
0
0
0
0
81
0
0
0
0
0
0
0
0
0
0
0
313155072
0
0
0
0
0
0
0
0
0
5400
0
10368
0
0
0
0
14580
0
0
0
217728
40310784
0
0
218700
0
0
0
0
1620
0
0
0
0
0
108
146304
0
0
0
466560
288
0
0
0
0
0
0
0
276138
0
0
0
0
0
0
0
52488...

result:

ok 332 tokens

Test #4:

score: 0
Accepted
time: 34ms
memory: 81932kb

input:

5
1000 0
1000 5
779 779 2
543 840 3
30 477 1
10 295 3
463 741 1
1000 6
379 569 1
249 826 2
194 819 3
90 400 1
614 808 2
102 868 2
1000 8
463 981 1
680 857 3
560 623 1
209 659 1
55 957 2
244 327 1
321 888 3
37 204 3
1000 5
336 851 3
410 676 1
522 911 2
165 962 1
258 330 3

output:

56888193
0
0
0
0

result:

ok 5 tokens

Test #5:

score: 0
Accepted
time: 37ms
memory: 81812kb

input:

5
1000 9
190 765 1
212 745 3
437 798 3
682 814 3
122 289 1
44 821 1
115 448 3
400 936 2
562 639 3
1000 5
561 808 3
23 160 2
57 915 2
211 943 3
125 596 2
1000 1
398 739 2
1000 3
629 973 2
7 721 2
591 815 2
1000 10
536 708 1
217 256 2
690 913 3
418 871 2
302 325 2
334 830 2
496 573 2
396 865 1
240 837...

output:

0
0
722271060
85306976
0

result:

ok 5 tokens

Test #6:

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

input:

2
2000 1
1501 1703 2
2000 5
1230 1521 3
1022 1939 3
1241 1283 3
767 1944 2
303 1163 3

output:

841960641
0

result:

ok 2 tokens

Test #7:

score: 0
Accepted
time: 85ms
memory: 161624kb

input:

2
2000 2
640 1942 1
1473 1917 3
2000 4
490 887 1
670 1163 3
824 1434 2
1221 1746 1

output:

0
0

result:

ok 2 tokens

Test #8:

score: -100
Memory Limit Exceeded

input:

1
5000 9
2821 3377 2
798 1535 2
3563 4161 3
2205 2946 3
1320 1594 3
278 1624 1
1243 2759 3
2882 4939 1
2639 3559 3

output:

0

result: