QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#499212#9155. 集合tanxi#100 ✓222ms35500kbC++141.6kb2024-07-31 08:49:242024-07-31 08:49:24

Judging History

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

  • [2024-07-31 08:49:24]
  • 评测
  • 测评结果:100
  • 用时:222ms
  • 内存:35500kb
  • [2024-07-31 08:49:24]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1.2e6+9;
int to[N];
int rd[N];
unsigned long long sum[N],sum1,sum2;
int a[N][3],b[N][3];
int n,m,q;
int f(int x)
{
	return x*x%998244353*x%998244353+x*1231%9982433+7;
}
bool check(int x)
{
	unsigned long long nows1=sum1,nows2=sum2;
	for(int j=0;j<3;j++)
	{
		nows1-=f(sum[a[x][j]]);
		nows1+=f(sum[a[x][j]]+rd[x]);
		nows2-=f(sum[b[x][j]]);
		nows2+=f(sum[b[x][j]]+rd[x]);
	}
	return nows1==nows2;
}
void add(int x)
{
	for(int j=0;j<3;j++)
	{
		sum1-=f(sum[a[x][j]]);
		sum[a[x][j]]+=rd[x];
		sum1+=f(sum[a[x][j]]);
		sum2-=f(sum[b[x][j]]);
		sum[b[x][j]]+=rd[x];
		sum2+=f(sum[b[x][j]]);
	}
}
void del(int x)
{
	for(int j=0;j<3;j++)
	{
		sum1-=f(sum[a[x][j]]);
		sum[a[x][j]]-=rd[x];
		sum1+=f(sum[a[x][j]]);
		sum2-=f(sum[b[x][j]]);
		sum[b[x][j]]-=rd[x];
		sum2+=f(sum[b[x][j]]);
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("ex_4.in","r",stdin);
	// freopen("1.out","w",stdout);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
	{
		rd[i]=rd[i+n]=i*1145141%1919810;
		sum1+=f(0);
		sum2+=f(0);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<3;j++)
		cin>>a[i][j];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<3;j++)
		{
			cin>>b[i][j];
			b[i][j]+=m;
		}
	}
	int r=1;
	for(int l=1;l<=n;l++)
	{
		while(r<=n&&check(r))
		{
			add(r);
			r++;
		}
		to[l]=r-1;
		del(l);
		if(r<=l)
		r=l+1;
	}
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		if(to[l]>=r)
		{
			cout<<"Yes\n";
		}
		else
		{
			cout<<"No\n";
		}
	}
	return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 0ms
memory: 9796kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 9764kb

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 9760kb

Pretest #4:

score: 5
Accepted
time: 1ms
memory: 9760kb

Pretest #5:

score: 5
Accepted
time: 1ms
memory: 9796kb

Pretest #6:

score: 5
Accepted
time: 1ms
memory: 9732kb

Pretest #7:

score: 5
Accepted
time: 1ms
memory: 9796kb

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 9772kb

Pretest #9:

score: 5
Accepted
time: 15ms
memory: 9804kb

Pretest #10:

score: 5
Accepted
time: 19ms
memory: 9772kb

Pretest #11:

score: 5
Accepted
time: 90ms
memory: 24936kb

Pretest #12:

score: 5
Accepted
time: 89ms
memory: 26296kb

Pretest #13:

score: 5
Accepted
time: 0ms
memory: 9752kb

Pretest #14:

score: 5
Accepted
time: 2ms
memory: 10004kb

Pretest #15:

score: 5
Accepted
time: 96ms
memory: 9776kb

Pretest #16:

score: 5
Accepted
time: 100ms
memory: 10004kb

Pretest #17:

score: 5
Accepted
time: 9ms
memory: 12288kb

Pretest #18:

score: 5
Accepted
time: 5ms
memory: 13188kb

Pretest #19:

score: 5
Accepted
time: 194ms
memory: 23544kb

Pretest #20:

score: 5
Accepted
time: 222ms
memory: 35384kb

Final Tests

Test #1:

score: 5
Accepted
time: 0ms
memory: 9860kb

Test #2:

score: 5
Accepted
time: 1ms
memory: 9764kb

Test #3:

score: 5
Accepted
time: 1ms
memory: 9708kb

Test #4:

score: 5
Accepted
time: 1ms
memory: 9700kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 9708kb

Test #6:

score: 5
Accepted
time: 1ms
memory: 9828kb

Test #7:

score: 5
Accepted
time: 1ms
memory: 9800kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 9868kb

Test #9:

score: 5
Accepted
time: 19ms
memory: 9780kb

Test #10:

score: 5
Accepted
time: 15ms
memory: 9856kb

Test #11:

score: 5
Accepted
time: 81ms
memory: 26160kb

Test #12:

score: 5
Accepted
time: 82ms
memory: 22948kb

Test #13:

score: 5
Accepted
time: 0ms
memory: 9884kb

Test #14:

score: 5
Accepted
time: 0ms
memory: 9920kb

Test #15:

score: 5
Accepted
time: 104ms
memory: 11880kb

Test #16:

score: 5
Accepted
time: 99ms
memory: 9848kb

Test #17:

score: 5
Accepted
time: 9ms
memory: 10344kb

Test #18:

score: 5
Accepted
time: 11ms
memory: 11200kb

Test #19:

score: 5
Accepted
time: 209ms
memory: 24852kb

Test #20:

score: 5
Accepted
time: 211ms
memory: 35500kb

Extra Test:

score: 0
Extra Test Passed