QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#403389#1286. Ternary String CountingcqbzlyWA 1ms3780kbC++142.8kb2024-05-02 10:28:162024-05-02 10:28:16

Judging History

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

  • [2024-05-02 10:28:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3780kb
  • [2024-05-02 10:28:16]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define ull unsigned long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=5005;
const int mod=1e9+7;
int T,n,m;
int f[N][N],a[N],b[N],c[N],d,a0[N],b0[N],c0[N],d0,pl[N],pr[N];
vector<pair<int,int>>q[N];
void add(int i,int j,int x){
    f[i][j]=(f[i][j]+x)%mod;
    a0[i]=(a0[i]+x)%mod;
    b0[j]=(b0[j]+x)%mod;
}
void del(int i,int j){
    int x=f[i][j];
    a0[i]=(a0[i]-x)%mod;
    b0[j]=(b0[j]-x)%mod;
    f[i][j]=0;
}
void sol(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)a[i]=b[i]=c[i]=0,q[i].clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=0;
        }
    }
    d=1;
    for(int i=1;i<=m;i++){
        int l,r,x;
        cin>>l>>r>>x;
        q[r].pb({l,x});
    }
    for(int i=1;i<=n;i++)pl[i]=1,pr[i]=i;
    int f1=1,f2=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i-1;j++)a0[j]=a[j],b0[j]=b[j],c0[j]=c[j];
        d0=0;
        for(int j=1;j<=i-2;j++){
            add(i-1,j,a[j]);
            add(i-1,j,b[j]);
            c0[i-1]=(c0[i-1]+c[j])%mod;
            add(i-1,j,c[j]);
        }
        c0[i-1]+=d;
        int l1=1,r1=i-1,l2=1,r2=i-1;
        for(auto j:q[i]){
            if(j.se==1){
                r1=min(r1,j.fi-1);
            }
            else if(j.se==2){
                f1=0;
                l2=max(l2,j.fi);
                r1=min(r1,j.fi-1);
            }
            else{
                f1=f2=0;
                l1=max(l1,j.fi);
            }
        }
        if(!f2){
            for(int j=1;j<=i-1;j++)c0[j]=0;
        }
        else{
            for(int j=r1+1;j<=i-1;j++)c0[j]=0;
        }
        if(f1)d0=1;
        if(l1>r1||l2>r2)l1=i,r1=i-1;
        for(int j=1;j<l1;j++){
            for(int k=pl[j];k<=pr[j];j++)del(j,k);
            pl[j]=1,pr[j]=0;
        }
        for(int j=l1;j<=r1;j++){
            if(max(pl[j],l2)>min(pr[j],r2)){
                for(int k=pl[j];k<=pr[j];j++)del(j,k);
                pl[j]=1,pr[j]=0;
            }
            else{
                while(pl[j]<l2)del(j,pl[j]),pl[j]++;
                while(pr[j]>r2)del(j,pr[j]),pr[j]--;
            }
        }
        for(int j=r1+1;j<=i-1;j++){
            for(int k=pl[j];k<=pr[j];k++)del(j,k);
            pl[j]=1,pr[j]=0;
        }
        for(int j=1;j<=i-1;j++)a[j]=a0[j],b[j]=b0[j],c[j]=c0[j];
        d=d0;
    }
    int res=d*3;
    for(int i=1;i<n;i++)res=(res+1ll*a[i]*6)%mod;
    for(int i=1;i<n;i++)res=(res+1ll*c[i]*6)%mod;
    cout<<(res+mod)%mod<<"\n";
}
int main(){
    //freopen("data.in","r",stdin);
    // freopen("own.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        sol();
    }
}

詳細信息

Test #1:

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

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

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:

0
0
12150
0
16254
0
0
18
1080
0
6
0
594
18
54
216
162
0
1572
1458
0
54
12
66
0
0
90
0
162
0
0
18
0
54
6
0
0
0
0
0
0
108
36450
1182
2916
999999791
0
90
0
0
0
0
0
6
0
324
8748
999999761
0
1458
0
0
0
4842
6
18
0
0
0
18
54
0
0
0
0
0
0
450
0
0
4374
54
450
162
324
6
0
0
0
0
18
54
0
0
0
0
12
0
0
0
0
0
0
0
...

result:

wrong answer 1st words differ - expected: '90', found: '0'