QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402901 | #1286. Ternary String Counting | Diu | WA | 1ms | 6004kb | C++14 | 1.5kb | 2024-05-01 17:23:48 | 2024-05-01 17:23:49 |
Judging History
answer
//
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5010,mod=1e9+7;
int T,n,m,l1[N],r1[N],l2[N],r2[N];
ll sl[N],sr[N],f[N][N];
int cx[N],cy[N];
void clr_f(int i,int k){
while(cx[i]<=k&&cx[i]<=cy[i]){
sl[i]=(sl[i]-f[i][cx[i]]+mod)%mod;
sr[cx[i]]=(sr[cx[i]]-f[i][cx[i]]+mod)%mod;
f[i][cx[i]]=0;
++cx[i];
}
}
void clr_b(int i,int k){
while(cy[i]>=k&&cx[i]<=cy[i]){
sl[i]=(sl[i]-f[i][cy[i]]+mod)%mod;
sr[cy[i]]=(sr[cy[i]]-f[i][cy[i]]+mod)%mod;
f[i][cy[i]]=0;
--cy[i];
}
}
signed main(){
scanf("%d",&T);
for(;T--;){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
sl[i]=sr[i]=0;
cx[i]=l1[i]=l2[i]=0;
cy[i]=i,r1[i]=r2[i]=i-1;
}
for(int i=1,l,r,x;i<=m;i++){
scanf("%d%d%d",&l,&r,&x);
if(x==1){
r1[r]=min(r1[r],l-1);
}else if(x==2){
l1[r]=max(l1[r],l);
r2[r]=min(r2[r],l-1);
}else{
l2[r]=max(l2[r],l);
}
}
f[0][0]=3;
sl[0]=sr[0]=3;
for(int i=2;i<=n;i++){
for(int j=0;j+1<i;j++){
f[i-1][j]=(sl[j]+sr[j])%mod;
sl[i-1]=(sl[i-1]+f[i-1][j])%mod;
sr[j]=(sr[j]+f[i-1][j])%mod;
}
for(int j=0;j<l1[i];j++)clr_f(j,j);
for(int j=l1[i];j<=r1[i];j++)clr_f(j,l2[i]-1),clr_b(j,r2[i]+1);
for(int j=r1[i]+1;j<i;j++)clr_f(j,j);
// printf("work:%d\n",i);
// printf("%d %d %d %d\n",l1[i],r1[i],l2[i],r2[i]);
// for(int j=0;j<i;j++){
// for(int k=0;k<=j;k++)if(f[j][k])printf("%d %d %d\n",j,k,f[j][k]);
// }
}
int ans=0;
for(int i=0;i<n;i++)ans=(ans+sl[i])%mod;
printf("%d\n",ans);
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6004kb
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: 5980kb
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 3 9 3 24309 27 3 3 1149 9 3 1107 2925 9 6579 927 3 3 21 3 3 3 3 3 9 9 3 3 27 3 147 9 9 9 3 9 4383 27 9 567 189 3 27 3 3033 3 3 9 9 3 3 3 3 3 189 345 9207 3 3 3 9 3 513 4329 3 3 9 27 21 3 3 21 81 3 3 27 3 3 3 2109 27 27 453 9 189 1845 3 3 3 3 3 57 9 27 3 3 3 165 1305 27 1899 351 729 3 45 45 3 9 69...
result:
wrong answer 2nd words differ - expected: '0', found: '3'