QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402951#1286. Ternary String CountingqwqUwU_TL 78ms101764kbC++172.2kb2024-05-01 18:23:152024-05-01 18:23:16

Judging History

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

  • [2024-05-01 18:23:16]
  • 评测
  • 测评结果:TL
  • 用时:78ms
  • 内存:101764kb
  • [2024-05-01 18:23:15]
  • 提交

answer

// clang-format off
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
typedef unsigned long long ull; 
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef pair<ll,ll> pll; typedef pair<int,ll> pil;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int mod=1e9+7;
inline void plust(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void minut(int &x,int y){x=x-y<0?x-y+mod:x-y;}
const int N=5002;
// clang-format on
int n,m;
vector<pii>vec[N];
int a[N][N],b[N],c[N],lp[N],rp[N];
inline void add(int i,int j,int k){
	plust(a[i][j],k);
	plust(b[i],k); plust(c[j],k);
}
inline void del(int i,int j){
	int x=a[i][j];a[i][j]=0;
	minut(b[i],x),minut(c[j],x);
}
int ans;
inline void solve(){
	n=read(),m=read();
	bool fl=0;
	rep(i,1,m){
		int l=read(),r=read(),x=read();
		if(l==1 && r==1 && x>1)fl=1;
		vec[r].pb(P(l,x));
	}
	if(fl){
		printf("0\n");
		goto clear;
	}
	add(0,0,1);
	lp[0]=rp[0]=0;
	rep(i,2,n){
		lp[i-1]=0,rp[i-1]=i-1;
		static int t[N];
		rep(j,0,i-1)t[j]=b[j]+c[j]>=mod?b[j]+c[j]-mod:b[j]+c[j];
		rep(j,0,i-1)add(i-1,j,t[j]);
		for(auto tmp:vec[i]){
			int lim=tmp.fi,x=tmp.se;
			if(x==1){
				rep(j,lim,i-1){
					rep(k,lp[j],rp[j])del(j,k);
					lp[j]=1,rp[j]=0;
				}
			}
			if(x==2){
				rep(j,0,lim-1){
					rep(k,lp[j],rp[j])del(j,k);
					lp[j]=1,rp[j]=0;
				}
				rep(j,0,i-1)while(rp[j]>=lim)del(j,rp[j]),--rp[j];
			}
			if(x==3){
				rep(j,0,i-1)while(lp[j]<lim) del(j,lp[j]),++lp[j];
			}
		}
	}
	ans=0;
	rep(j,0,n-1)plust(ans,3ll*b[j]%mod);
	printf("%d\n",ans);


clear:


	rep(i,0,n)rep(j,0,n)a[i][j]=0;
	rep(i,0,n)b[i]=c[i]=0;
	rep(i,1,n)vec[i].clear();
}
int main() {
    //freopen("data.in", "r", stdin);
    // freopen(".in","r",stdin);
    // freopen("myans.out","w",stdout);
	int T=read();while(T--)solve();
    return 0;
}

詳細信息

Test #1:

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

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: 1ms
memory: 3868kb

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

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: 9ms
memory: 11832kb

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: 14ms
memory: 11840kb

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: 7ms
memory: 27580kb

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: 12ms
memory: 27512kb

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: 0
Accepted
time: 78ms
memory: 101716kb

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:

ok "0"

Test #9:

score: 0
Accepted
time: 60ms
memory: 101652kb

input:

1
5000 2
539 4252 1
906 3821 1

output:

101862333

result:

ok "101862333"

Test #10:

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

input:

111
34 0
30 0
18 0
35 0
3 0
43 0
13 0
28 0
57 0
75 0
31 0
4 0
92 0
1 0
53 0
85 0
74 0
43 0
59 0
72 0
79 0
40 0
70 0
36 0
86 0
56 0
53 0
66 0
50 0
100 0
60 0
74 0
50 0
51 0
92 0
49 0
50 0
78 0
95 0
4 0
59 0
44 0
92 0
84 0
7 0
75 0
99 0
56 0
54 0
13 0
27 0
33 0
22 0
80 0
14 0
79 0
29 0
39 0
21 0
97 0
...

output:

582926302
130653412
387420489
748778899
27
738321955
1594323
792294829
998064805
100094381
391960236
81
587240675
3
172815616
473062299
700031465
738321955
982583189
966670169
107644805
953271190
662963356
246336683
419186890
666021604
172815616
909419307
710104287
886041711
947749553
700031465
7101...

result:

ok 111 tokens

Test #11:

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

input:

16
350 0
453 0
485 0
361 0
498 0
149 0
433 0
435 0
279 0
240 0
166 0
152 0
393 0
159 0
219 0
222 0

output:

378029361
68761795
621961191
766744305
24977444
679213660
705815658
352340880
186665231
458529104
150230246
338768694
907169137
887128598
322586612
709838468

result:

ok 16 tokens

Test #12:

score: 0
Accepted
time: 41ms
memory: 101764kb

input:

1
5000 0

output:

22443616

result:

ok "22443616"

Test #13:

score: -100
Time Limit Exceeded

input:

1
5000 1000000
4736 4854 3
405 1465 3
835 4720 3
633 1954 3
2182 4257 3
1920 3098 3
302 3157 3
63 3964 3
4032 4116 3
734 1980 3
1083 4515 3
44 4768 3
20 4466 3
1160 2774 3
794 1531 3
2301 4714 3
255 4939 3
2699 2967 3
1835 2733 3
582 2071 3
430 1857 3
249 2013 3
922 4833 3
13 1973 3
3150 3812 3
2904...

output:


result: