QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402920#1286. Ternary String CountingqwqUwU_WA 1ms4132kbC++172.4kb2024-05-01 17:37:492024-05-01 17:37:50

Judging History

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

  • [2024-05-01 17:37:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4132kb
  • [2024-05-01 17:37:49]
  • 提交

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'