QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#405396#1286. Ternary String CountingTulipeNoireWA 1ms3784kbC++142.8kb2024-05-05 20:43:032024-05-05 20:43:04

Judging History

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

  • [2024-05-05 20:43:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3784kb
  • [2024-05-05 20:43:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const int N=5005,mod=1000000007;
struct Matrix {
    int l1,r1,l2,r2;
    inline Matrix operator*(const Matrix o) {
        return {max(l1,o.l1),min(r1,o.r1),max(l2,o.l2),min(r2,o.r2)};
    }
}mat[N];
int n,m;
int Lj,Lk[N],Rk[N];
int Sj[N],Sk[N],f[N][N];
inline void solve() {
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) mat[i]={0,n,0,n};
    while (m--) {
        int l,r,c;
        scanf("%d %d %d",&l,&r,&c);
        Matrix x;
        if (c==1) x={0,l-1,0,l-1};
        else if (c==2) x={l,n,0,l-1};
        else x={l+1,n,l,n};
        mat[r]=mat[r]*x;
    }
    // for (int i=1;i<=n;i++) {
    //     printf("%d %d %d %d\n",mat[i].l1,mat[i].r1,mat[i].l2,mat[i].r2);
    // }
    if (mat[1].l1!=0) {
        puts("0");
        return;
    }
    Lj=0;
    for (int i=0;i<=n;i++) Lk[i]=0,Rk[i]=n;
    for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) f[i][i]=0;
    for (int i=0;i<=n;i++) Sj[i]=Sk[i]=0;
    f[0][0]=Sj[0]=Sk[0]=3;
    for (int i=1;i<n;i++) {
        for (int k=0;k<i;k++) {
            int d=(Sj[k]+Sk[k])%mod;
            f[i][k]=d,Sk[k]=(Sk[k]+d)%mod,Sj[i]=(Sj[i]+d)%mod;
        }
        for (int j=0;j<mat[i+1].l1&&j<=i;j++) {
            Sj[j]=0;
            for (int k=Lk[j];k<=Rk[j];k++) {
                Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
                f[j][k]=0;
            }
            Lk[j]=n,Rk[j]=0;
        }
        for (int j=mat[i+1].r1+1;j<=i;j++) {
            Sj[j]=0;
            for (int k=Lk[j];k<=Rk[j];k++) {
                Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
                f[j][k]=0;
            }
            Lk[j]=n,Rk[j]=0;
        }
        for (int j=mat[i+1].l1;j<=i&&j<=mat[i+1].r1;j++) {
            int L=max(Lk[j],mat[i+1].l2);
            int R=min(Rk[j],mat[i+1].r2);
            if (L>R) {
                Sj[j]=0;
                for (int k=Lk[j];k<=Rk[j];k++) {
                    Sk[k]=(Sk[k]-f[j][k]+mod)%mod;
                    f[j][k]=0;
                }
                Lk[j]=n,Rk[j]=0;
            } else {
                for (int k=Lk[j];k<L;k++) Sj[j]=(Sj[j]-f[j][k]+mod)%mod,Sk[k]=(Sk[k]-f[j][k]+mod)%mod,f[j][k]=0;
                for (int k=R+1;k<=Rk[j];k++) Sj[j]=(Sj[j]-f[j][k]+mod)%mod,Sk[k]=(Sk[k]-f[j][k]+mod)%mod,f[j][k]=0;
                Lk[j]=L,Rk[j]=R;
            }
        }
    }
    // for (int i=0;i<=n;i++) {
    //     for (int j=0;j<=n;j++) {
    //         printf("%d ",f[i][j]);
    //     }
    //     puts("");
    // }
    int ans=0;
    for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) ans=(ans+f[i][j])%mod;
    printf("%d\n",ans);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
    freopen("err", "w", stderr);
#endif
    int T;
    scanf("%d",&T);
    while (T--) solve();
    return 0;
}

详细

Test #1:

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

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

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
60
0
0
24300
0
0
0
25068
24
384
25272
3564
1944
6480
864
144
0
0
0
0
0
0
0
6
0
0
0
0
0
96
96
6
0
0
0
0
0
576
0
108
576
0
0
2916
216
216
648
648
0
0
0
0
0
0
324
8748
1944
0
5832
0
0
0
4320
18
0
18
18
0
18
18
2880
0
0
0
0
0
0
0
1992
996
996
450
300
162
1956
108
0
0
0
864
54
54
72
12
0
300
0
1044
96...

result:

wrong answer 2nd words differ - expected: '0', found: '60'