QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#697823 | #1286. Ternary String Counting | pzjQWQ | ML | 326ms | 202468kb | C++14 | 2.3kb | 2024-11-01 15:54:45 | 2024-11-01 15:54:45 |
Judging History
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