QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#503197 | #9155. 集合 | Flamire | 100 ✓ | 200ms | 22276kb | C++20 | 1.2kb | 2024-08-03 16:56:32 | 2024-08-03 16:56:33 |
Judging History
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