QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489435#9155. 集合clly100 ✓264ms28664kbC++141.5kb2024-07-24 20:07:532024-07-24 20:07:54

Judging History

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

  • [2024-07-24 20:07:54]
  • 评测
  • 测评结果:100
  • 用时:264ms
  • 内存:28664kb
  • [2024-07-24 20:07:53]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long 
#define ull unsigned long long 
#define ld double 
using namespace std;
const ll N=2e5+100,M=6e5+100;
inline ll read();
ll a[N][3],b[N][3],mp[M],R[N],msk,q,n,m,T;
ull s1,s2,ap[M],bp[M];
ull rd(ull x)
{
	x=x;
	x=x*1331;
	x=x^msk;
	x=x*13;
	x=x^msk;
	x=x*131;
	return x;
}
void add(ll x,ll w)
{
	for(int i=0;i<=2;i++)
	{
		s1=s1-rd(ap[a[x][i]]);
		ap[a[x][i]]=ap[a[x][i]]+w*mp[x];
		s1=s1+rd(ap[a[x][i]]);
	}
	for(int i=0;i<=2;i++)
	{
		s2=s2-rd(bp[b[x][i]]);
		bp[b[x][i]]=bp[b[x][i]]+w*mp[x];
		s2=s2+rd(bp[b[x][i]]);
	}
}
void solve()
{
	s1=0,s2=0;
	msk=rand(); 
	for(int i=1;i<=n;i++)
	{
		mp[i]=rand()*rand()+rand();
	}
	for(int i=1;i<=m;i++)
	  ap[i]=bp[i]=0;
	add(1,1);
	for(int i=1,j=0;i<=n;add(i,-1),i++)
	{
		while(s1==s2&&j<n)
		{
			j++;
			add(j+1,1);
		}
		R[i]=min(R[i],(ll)j);
	}
	return ;
}
int main()
{
	srand(20090302);
	n=read(),m=read(),q=read();
	for(int i=1;i<=n;i++)  
	  for(int j=0;j<=2;j++) a[i][j]=read();
	for(int i=1;i<=n;i++)
	  for(int j=0;j<=2;j++) b[i][j]=read();
	for(int i=1;i<=n;i++) R[i]=n;
	T=15;
	while(T--)
	  solve();
	ll l,r;
	while(q--)
	{
		l=read(),r=read();
		if(r<=R[l]) printf("Yes\n");
		else printf("No\n"); 
	}
	return 0; 
}
inline ll read()
{
	ll w=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w*f;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 12ms
memory: 13904kb

Pretest #10:

score: 5
Accepted
time: 8ms
memory: 13928kb

Pretest #11:

score: 5
Accepted
time: 168ms
memory: 23008kb

Pretest #12:

score: 5
Accepted
time: 161ms
memory: 19452kb

Pretest #13:

score: 5
Accepted
time: 4ms
memory: 16040kb

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 54ms
memory: 13996kb

Pretest #16:

score: 5
Accepted
time: 55ms
memory: 14036kb

Pretest #17:

score: 5
Accepted
time: 13ms
memory: 13908kb

Pretest #18:

score: 5
Accepted
time: 20ms
memory: 16480kb

Pretest #19:

score: 5
Accepted
time: 228ms
memory: 19748kb

Pretest #20:

score: 0
Wrong Answer
time: 264ms
memory: 28664kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 165ms
memory: 20312kb

Test #12:

score: 5
Accepted
time: 162ms
memory: 21248kb

Test #13:

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

Test #14:

score: 5
Accepted
time: 4ms
memory: 14020kb

Test #15:

score: 5
Accepted
time: 50ms
memory: 13932kb

Test #16:

score: 5
Accepted
time: 46ms
memory: 12052kb

Test #17:

score: 5
Accepted
time: 14ms
memory: 11872kb

Test #18:

score: 5
Accepted
time: 20ms
memory: 16488kb

Test #19:

score: 5
Accepted
time: 228ms
memory: 22620kb

Test #20:

score: 5
Accepted
time: 264ms
memory: 26552kb