QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402956#1286. Ternary String CountingslenbolTL 24ms104932kbC++142.1kb2024-05-01 18:50:042024-05-01 18:50:05

Judging History

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

  • [2024-05-01 18:50:05]
  • 评测
  • 测评结果:TL
  • 用时:24ms
  • 内存:104932kb
  • [2024-05-01 18:50:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;T f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-')f=-1;
	for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;
}
template <typename T,typename ...Args>void read(T &x,Args&...args){read(x),read(args...);}
template <typename T> void print(T x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) print(x/10);
	putchar(x%10+48);
}
template <typename T> void print(T x,char c){print(x); putchar(c);}
template<typename T>inline void output(T x){print(x,' ');}
template<typename T,typename ...Arg>inline void output(T x,Arg ...arg){output(x);output(arg...);}
const int N=5007,mod=1e9+7;
deque<int>q[N];
int T,n,m,ans,L1[N],R1[N],L2[N],R2[N],row[N],col[N],f[N][N];
void update(int x,int y,int z)
{
	q[y].push_back(x);
	row[x]=(row[x]+z)%mod;
	col[y]=(col[y]+z)%mod;
	f[x][y]=(f[x][y]+z)%mod;
}
void clear_front(int y)
{
	int x=q[y].front();
	q[y].pop_front();
	row[x]=(row[x]-f[x][y]+mod)%mod;
	col[y]=(col[y]-f[x][y]+mod)%mod;
	f[x][y]=0;
}
void clear_back(int y)
{
	int x=q[y].back();
	q[y].pop_back();
	row[x]=(row[x]-f[x][y]+mod)%mod;
	col[y]=(col[y]-f[x][y]+mod)%mod;
	f[x][y]=0;
}
void solve()
{
	read(n,m);
	memset(row,0,sizeof row);
	memset(col,0,sizeof col);
	memset(f,0,sizeof f);
	for(int i=0;i<n;i++) q[i].clear();
	for(int i=1;i<=n;i++)
		L1[i]=L2[i]=0,
		R1[i]=R2[i]=i-1;
	for(int i=1,l,r,x;i<=m;i++)
	{
		read(l,r,x);
		if(x==1) R1[r]=min(R1[r],l-1);
		if(x==2)
		{
			L1[r]=max(L1[r],l);
			R2[r]=min(R2[r],l-1);
		}
		if(x==3) L2[r]=max(L2[r],l);
	}
	update(0,0,1); ans=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<max(i-1,1);j++)
			update(i-1,j,(row[j]+col[j])%mod);
		for(int j=0;j<i;j++)
			if(L2[i]<=j&&j<=R2[i])
			{
				while(q[j].size()&&q[j].front()<L1[i]) clear_front(j);
				while(q[j].size()&&q[j].back()>R1[i]) clear_back(j);
			}
			else while(q[j].size()) clear_front(j);
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			ans=(ans+f[i][j])%mod;
	print(ans,'\n');
}
int main()
{
	read(T);
	while(T--) solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 24ms
memory: 104932kb

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...

output:


result: