QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#495200#9155. 集合Actuct100 ✓401ms59200kbC++141.6kb2024-07-27 19:26:302024-07-27 19:26:35

Judging History

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

  • [2024-07-27 19:26:35]
  • 评测
  • 测评结果:100
  • 用时:401ms
  • 内存:59200kb
  • [2024-07-27 19:26:30]
  • 提交

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++)
	{
		while(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: 1ms
memory: 10036kb

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 267ms
memory: 13568kb

Pretest #12:

score: 5
Accepted
time: 263ms
memory: 13324kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 92ms
memory: 10036kb

Pretest #16:

score: 5
Accepted
time: 93ms
memory: 10436kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 26ms
memory: 14564kb

Pretest #19:

score: 5
Accepted
time: 373ms
memory: 12920kb

Pretest #20:

score: 5
Accepted
time: 393ms
memory: 59156kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 268ms
memory: 12560kb

Test #12:

score: 5
Accepted
time: 267ms
memory: 13128kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 108ms
memory: 9840kb

Test #16:

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

Test #17:

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

Test #18:

score: 5
Accepted
time: 26ms
memory: 14640kb

Test #19:

score: 5
Accepted
time: 382ms
memory: 13824kb

Test #20:

score: 5
Accepted
time: 401ms
memory: 59200kb

Extra Test:

score: 0
Extra Test Passed