QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#697823#1286. Ternary String CountingpzjQWQML 326ms202468kbC++142.3kb2024-11-01 15:54:452024-11-01 15:54:45

Judging History

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

  • [2024-11-01 15:54:45]
  • 评测
  • 测评结果:ML
  • 用时:326ms
  • 内存:202468kb
  • [2024-11-01 15:54:45]
  • 提交

answer

#include<bits/stdc++.h>
#define endl '\n'
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=5005,mod=1e9+7;
int T,n,m,f[N][N<<2],p[N][5][2];
bool tag[N][N<<2];
void build(int x,int p,int l,int r){
	f[x][p]=tag[x][p]=0;
	if(l==r) return;
	int mid=l+r>>1;
	build(x,ls,l,mid),build(x,rs,mid+1,r);
}
void pushdown(int x,int p,int l,int r){
	int mid=l+r>>1;
	if(tag[x][p]){
		tag[x][ls]=tag[x][rs]=1,f[x][ls]=f[x][rs]=0;
		tag[x][p]=0;
	}
}
void update(int x,int p,int l,int r,int ql,int qr){
	if(!f[x][p]) return;
	if(ql<=l&&r<=qr){
		f[x][p]=0;
		tag[x][p]=1;
		return;
	}
	pushdown(x,p,l,r);
	int mid=l+r>>1;
	if(ql<=mid) update(x,ls,l,mid,ql,qr);
	if(mid<qr) update(x,rs,mid+1,r,ql,qr);
	f[x][p]=(f[x][ls]+f[x][rs])%mod;
}
void add(int x,int p,int l,int r,int pos,int w){
	if(!w) return;
	f[x][p]=(f[x][p]+w)%mod;
	if(l==r) return;
	pushdown(x,p,l,r);
	int mid=l+r>>1;
	if(pos<=mid) add(x,ls,l,mid,pos,w);
	else add(x,rs,mid+1,r,pos,w);
}
void init(int r){
	for(int i=0;i<r;++i){
		int L=-1,R=n;
		if(~p[r][1][0]){
			if(i>=p[r][1][0]){
				update(i,1,0,n-1,0,n-1);
				continue;
			} else R=min(R,p[r][1][0]);
		}
		if(~p[r][3][1]){
			if(i>=p[r][3][1]) L=max(L,p[r][3][1]-1);
			else{
				update(i,1,0,n-1,0,n-1);
				continue;
			}
		}
		if(~p[r][2][0]){
			if(i>=p[r][2][0]) R=min(R,p[r][2][0]);
			else L=max(L,p[r][2][0]-1);
		}
		if(~p[r][2][1]){
			if(i>=p[r][2][1]) R=min(R,p[r][2][1]);
			else L=max(L,p[r][2][1]-1);
		}
		if(L>=R) update(i,1,0,n-1,0,n-1);
		else{
			if(L!=-1) update(i,1,0,n-1,0,L);
			if(R!=n) update(i,1,0,n-1,R,n-1);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;++i) memset(p[i],-1,sizeof(p[i]));
		while(m--){
			int l,r,x;
			cin>>l>>r>>x;
			if(p[r][x][0]==-1) p[r][x][0]=p[r][x][1]=l;
			else p[r][x][0]=min(p[r][x][0],l),p[r][x][1]=max(p[r][x][1],l);
		}
		for(int i=0;i<n;++i) build(i,1,0,n-1);
		add(0,1,0,n-1,0,1),init(1);
		for(int i=2;i<=n;++i){
			for(int j=0;j<i-1;++j){
				add(i-1,1,0,n-1,j,f[j][1]);
				add(j,1,0,n-1,i-1,f[j][1]);
			}
			init(i);
		}
		int ans=0;
		for(int i=0;i<n;++i) ans=(ans+f[i][1])%mod;
		cout<<3ll*ans%mod<<endl;
	}
	return 0;
}

详细

Test #1:

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

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

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

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

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

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

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

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: