QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402817 | #1286. Ternary String Counting | dengziyue | TL | 59ms | 199388kb | C++14 | 2.1kb | 2024-05-01 15:54:23 | 2024-05-01 15:54:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define max_n 5000
#define mod 1000000007ll
int tid;
int n;
int m;
struct L{int l1,r1,l2,r2;};
vector<L>lim[max_n+2];
long long dp[max_n+2][max_n+2];
long long sx[max_n+2];
long long sy[max_n+2];
long long ans=0;
inline void upd(int x,int y,long long w){
dp[x][y]=(dp[x][y]+w)%mod; sx[x]=(sx[x]+w)%mod; sy[y]=(sy[y]+w)%mod;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("QOJ1286_1.in","r",stdin);
freopen("QOJ1286_1.out","w",stdout);
#endif
scanf("%d",&tid);
for(int ca=1;ca<=tid;++ca){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)lim[i].clear();
bool ok=true;
for(int i=1,l,r,w;i<=m;++i){
scanf("%d%d%d",&l,&r,&w);
if(r-l+1<w)ok=false;
if(w==1)lim[r].push_back((L){0,l-1,0,l-1});
if(w==2)lim[r].push_back((L){l,r-1,0,l-1});
if(w==3)lim[r].push_back((L){l,r-1,l,r-1});
}
if(!ok){printf("0\n"); continue;}
memset(dp,0,sizeof(dp));
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
dp[0][0]=sx[0]=sy[0]=3;
int nowl1=0,nowr1=n,nowl2=0,nowr2=n;
for(int i=2;i<=n&&nowl1<=nowr1&&nowl2<=nowr2;++i){
vector<pair<pair<int,int>,long long>>op;
for(int j=0;j<=n;++j)op.push_back({{i-1,j},sx[j]});
for(int k=0;k<=n;++k)op.push_back({{i-1,k},sy[k]});
for(auto u:op)upd(u.first.first,u.first.second,u.second);
for(auto u:lim[i]){
int tol1=max(nowl1,u.l1),tor1=min(nowr1,u.r1),tol2=max(nowl2,u.l2),tor2=min(nowr2,u.r2);
if(tol1>tor1||tol2>tor2){nowl1=tol1; nowr1=tor1; nowl2=tol2; nowr2=tor2; break;}
for(int j=nowl1;j<=tol1-1;++j){
for(int k=nowl2;k<=nowr2;++k)upd(j,k,mod-dp[j][k]);
}
for(int j=tol1;j<=tor1;++j){
for(int k=nowl2;k<=tol2-1;++k)upd(j,k,mod-dp[j][k]);
for(int k=tor2+1;k<=nowr2;++k)upd(j,k,mod-dp[j][k]);
}
for(int j=tor1+1;j<=nowr1;++j){
for(int k=nowl2;k<=nowr2;++k)upd(j,k,mod-dp[j][k]);
}
}
}
if(nowl1<=nowr1&&nowl2<=nowr2){
ans=0;
for(int i=nowl1;i<=nowr1;++i){
for(int j=nowl2;j<=nowr2;++j)ans=(ans+dp[i][j])%mod;
}
printf("%lld\n",(ans%mod+mod)%mod);
}
else printf("0\n");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 59ms
memory: 199388kb
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
Time Limit Exceeded
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...