QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#503197#9155. 集合Flamire100 ✓200ms22276kbC++201.2kb2024-08-03 16:56:322024-08-03 16:56:33

Judging History

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

  • [2024-08-03 16:56:33]
  • 评测
  • 测评结果:100
  • 用时:200ms
  • 内存:22276kb
  • [2024-08-03 16:56:32]
  • 提交

answer

#include <bits/stdc++.h>
#define N 600011
#define ull unsigned long long
#define pii pair<int,int>
#define s1 first
#define s2 second
using namespace std;
int a[N],b[N],n,m,q;
mt19937_64 rnd(801);
const int B=1000;
struct kueri
{
	int l,r,lb,id;
};
bool cmp(kueri a,kueri b){return a.lb==b.lb?a.r<b.r:a.lb<b.lb;}
vector<kueri> vk;
ull ha[N],HA,hb[N],HB,V[N];
int ans[1000011],bb[N];
void moda(int x,int i)
{
	HA-=ha[a[x]];
	ha[a[x]]^=V[i];
	HA+=ha[a[x]];
}
void modb(int x,int i)
{
	HB-=hb[b[x]];
	hb[b[x]]^=V[i];
	HB+=hb[b[x]];
}
int f[N];
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=3*n;++i)scanf("%d",a+i);
	for(int i=1;i<=3*n;++i)scanf("%d",b+i);
	for(int i=1;i<=n;++i)V[i]=rnd();
	int L=1;
	for(int i=1;i<=n;++i)
	{
		moda(3*i-2,i);
		moda(3*i-1,i);
		moda(3*i,i);
		modb(3*i-2,i);
		modb(3*i-1,i);
		modb(3*i,i);
		while(HA!=HB)
		{
			moda(3*L-2,L);
			moda(3*L-1,L);
			moda(3*L,L);
			modb(3*L-2,L);
			modb(3*L-1,L);
			modb(3*L,L);
			++L;
		}
		f[i]=L;
	}
	for(int i=1;i<=q;++i)
	{
		int l,r;scanf("%d%d",&l,&r);
		printf(f[r]<=l?"Yes\n":"No\n");
	}
	fclose(stdin);fclose(stdout);return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 73ms
memory: 11616kb

Pretest #12:

score: 5
Accepted
time: 71ms
memory: 12672kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 105ms
memory: 9908kb

Pretest #16:

score: 5
Accepted
time: 105ms
memory: 10040kb

Pretest #17:

score: 5
Accepted
time: 7ms
memory: 9980kb

Pretest #18:

score: 5
Accepted
time: 3ms
memory: 12948kb

Pretest #19:

score: 5
Accepted
time: 189ms
memory: 14808kb

Pretest #20:

score: 5
Accepted
time: 200ms
memory: 22136kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 72ms
memory: 14064kb

Test #12:

score: 5
Accepted
time: 56ms
memory: 14720kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 109ms
memory: 9948kb

Test #16:

score: 5
Accepted
time: 114ms
memory: 10052kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 185ms
memory: 14080kb

Test #20:

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

Extra Test:

score: 0
Extra Test Passed