QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402920 | #1286. Ternary String Counting | qwqUwU_ | WA | 1ms | 4132kb | C++17 | 2.4kb | 2024-05-01 17:37:49 | 2024-05-01 17:37:50 |
Judging History
answer
// clang-format off
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
mt19937 gen(time(0));
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef pair<ll,ll> pll; typedef pair<int,ll> pil;
inline ll read(){
ll x=0,f=1,c=getchar();
while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int mod=1e9+7;
inline void plust(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void minut(int &x,int y){x=x-y<0?x-y+mod:x-y;}
const int N=5001;
// clang-format on
int n,m;
vector<pii>vec[N];
int a[N][N],b[N],c[N],l[N][N],u[N][N],r[N][N],d[N][N];
inline void add(int i,int j,int k){
plust(a[i][j],k);
plust(b[i],k); plust(c[j],k);
}
inline void del(int i,int j){
int x=a[i][j];a[i][j]=0;
minut(b[i],x),minut(c[j],x);
int p=d[i][j],q=u[i][j];
u[p][j]=q;
if(~q)d[q][j]=p;
p=l[i][j],q=r[i][j];
l[i][q]=p;
if(~p)r[i][p]=q;
}
int ans;
inline void solve(){
n=read(),m=read();
bool fl=0;
rep(i,1,m){
int l=read(),r=read(),x=read();
if(l==1 && r==1 && x>1)fl=1;
vec[r].pb(P(l,x));
}
if(fl){
printf("0\n");
goto clear;
}
rep(i,0,n)rep(j,0,n)l[i][j]=j-1,u[i][j]=i-1;
rep(i,0,n)rep(j,0,n)r[i][j]=j+1,d[i][j]=i+1;
add(0,0,1);
rep(i,2,n){
static int tb[N],tc[N];
rep(j,0,i-1)tb[j]=b[j],tc[j]=c[j];
rep(k,0,i-1)add(i-1,k,tc[k]);
rep(j,0,i-1)add(i-1,j,tb[j]);
for(auto tmp:vec[i]){
int lim=tmp.fi,x=tmp.se;
if(x==1){
rep(j,lim,i-1)for(int k=l[j][n];~k;k=l[j][n])del(j,k);
}
if(x==2){
rep(j,0,lim-1)for(int k=l[j][n];~k;k=l[j][k])del(j,k);
rep(k,lim,i-1)for(int j=u[n][k];~j;j=u[j][k])del(j,k);
}
if(x==3){
rep(k,0,lim-1)for(int j=u[n][k];~j;j=u[j][k])del(j,k);
}
}
}
ans=0;
rep(j,0,n-1)plust(ans,3ll*b[j]%mod);
printf("%d\n",ans);
clear:
rep(i,0,n)rep(j,0,n)a[i][j]=l[i][j]=u[i][j]=r[i][j]=d[i][j]=0;
rep(i,0,n)b[i]=c[i]=0;
rep(i,1,n)vec[i].clear();
}
int main() {
//freopen("data.in", "r", stdin);
// freopen(".in","r",stdin);
// freopen("myans.out","w",stdout);
int T=read();while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4032kb
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: 0ms
memory: 4132kb
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 3018 0 0 972 2916 378 18144 13662 0 0 0 0 0 0 0 0 6 1134 162 18 0 90 420 162 6 0 162 0 0 0 126 0 162 0 0 0 2916 0 0 0 0 0 1944 0 0 0 2430 324 8748 324 6 0 0 0 0 4320 18 0 0 36 0 0 0 0 0 0 0 3726 0 0 0 4824 0 0 450 0 162 3870 0 0 0 0 0 162 0 18 0 0 3402 0 1884 0 5346 540 0 0 54 3...
result:
wrong answer 9th words differ - expected: '768', found: '3018'