QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491752#9155. 集合Gaode_Sean100 ✓400ms59272kbC++171.6kb2024-07-25 21:47:462024-07-25 21:47:46

Judging History

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

  • [2024-07-25 21:47:46]
  • 评测
  • 测评结果:100
  • 用时:400ms
  • 内存:59272kb
  • [2024-07-25 21:47:46]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,M=6e5+5;
int n,m,q;
int a[N][4],b[N][4],mx[N];
ll res;
ll w[N],rs[5],ca[M][5],cb[M][5],mod[5]={0,998244353,1000000001,1000000003,1000000007};
void add_a(int pos,int x,ll val)
{
	for(int i=1;i<=4;i++)
	{
		rs[i]=(rs[i]-ca[a[pos][x]][i]*ca[a[pos][x]][i]%mod[i]*ca[a[pos][x]][i]%mod[i]+mod[i])%mod[i];
		ca[a[pos][x]][i]=(ca[a[pos][x]][i]+val*w[pos]+mod[i])%mod[i];
		rs[i]=(rs[i]+ca[a[pos][x]][i]*ca[a[pos][x]][i]%mod[i]*ca[a[pos][x]][i]%mod[i]+mod[i])%mod[i];
	}
	res=0;
	for(int i=1;i<=4;i++) res+=rs[i];
}
void add_b(int pos,int x,ll val)
{
	for(int i=1;i<=4;i++)
	{
		rs[i]=(rs[i]+cb[b[pos][x]][i]*cb[b[pos][x]][i]%mod[i]*cb[b[pos][x]][i]%mod[i]+mod[i])%mod[i];
		cb[b[pos][x]][i]=(cb[b[pos][x]][i]+val*w[pos]+mod[i])%mod[i];
		rs[i]=(rs[i]-cb[b[pos][x]][i]*cb[b[pos][x]][i]%mod[i]*cb[b[pos][x]][i]%mod[i]+mod[i])%mod[i];
	}
	res=0;
	for(int i=1;i<=4;i++) res+=rs[i];
}
void calc(int pos,int val)
{
	for(int i=1;i<=3;i++) add_a(pos,i,val),add_b(pos,i,val);
}
int rando(){return (1ll*rand()*rand()+1ll*rand()*rand()*rand())%998244353;}
int main()
{
	scanf("%d%d%d",&n,&m,&q),srand((unsigned)time(0));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++) scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++) scanf("%d",&b[i][j]);
	}
	for(int i=1;i<=n;i++) w[i]=rando();
	for(int l=1,r=0;l<=n;l++)
	{
		for(;r<=n&&!res;calc(++r,1));
		mx[l]=r-1,calc(l,-1);
	}
	for(int i=1,l,r;i<=q;i++) scanf("%d%d",&l,&r),puts(mx[l]>=r?"Yes":"No");
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

score: 5
Accepted
time: 21ms
memory: 10032kb

Pretest #11:

score: 5
Accepted
time: 275ms
memory: 12792kb

Pretest #12:

score: 5
Accepted
time: 273ms
memory: 13596kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 102ms
memory: 9892kb

Pretest #16:

score: 5
Accepted
time: 103ms
memory: 12356kb

Pretest #17:

score: 5
Accepted
time: 23ms
memory: 10020kb

Pretest #18:

score: 5
Accepted
time: 27ms
memory: 14528kb

Pretest #19:

score: 5
Accepted
time: 375ms
memory: 13892kb

Pretest #20:

score: 5
Accepted
time: 400ms
memory: 59272kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 16ms
memory: 9880kb

Test #10:

score: 5
Accepted
time: 17ms
memory: 10008kb

Test #11:

score: 5
Accepted
time: 265ms
memory: 12724kb

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 102ms
memory: 9896kb

Test #16:

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

Test #17:

score: 5
Accepted
time: 23ms
memory: 9968kb

Test #18:

score: 5
Accepted
time: 27ms
memory: 16688kb

Test #19:

score: 5
Accepted
time: 383ms
memory: 14012kb

Test #20:

score: 5
Accepted
time: 392ms
memory: 59192kb

Extra Test:

score: 0
Extra Test Passed