QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492282 | #9155. 集合 | C1942huangjiaxu | 100 ✓ | 57ms | 28224kb | C++14 | 1.1kb | 2024-07-26 11:07:37 | 2024-07-26 11:07:38 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
mt19937_64 rnd(0x66ccff);
typedef unsigned long long ull;
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
template<class rd>
void read(rd &x){
char c=getchar();
for(;c<48||c>57;c=getchar());
for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48);
}
int n,m,q,a[N][3],b[N][3],p[N];
ull val(ull x){
x^=x<<13;
x^=x>>7;
x^=x<<17;
return x+0x66ccff;
}
ull w[N],va,vb,wa[N*3],wb[N*3];
void add(int x,int o){
for(int j=0,v;j<3;++j){
v=a[x][j];
va-=val(wa[v]);
wa[v]+=w[x]*o;
va+=val(wa[v]);
v=b[x][j];
vb-=val(wb[v]);
wb[v]+=w[x]*o;
vb+=val(wb[v]);
}
}
int main(){
read(n),read(m),read(q);
for(int i=1;i<=n;++i)for(int j=0;j<3;++j)read(a[i][j]);
for(int i=1;i<=n;++i)for(int j=0;j<3;++j)read(b[i][j]);
for(int i=1;i<=n;++i)w[i]=rnd();
for(int i=n,j=n;i;--i){
add(i,1);
while(va!=vb)add(j--,-1);
p[i]=j;
}
for(int i=1,l,r;i<=q;++i){
read(l),read(r);
puts(p[l]>=r?"Yes":"No");
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 11868kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 11876kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 11892kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 11892kb
Pretest #5:
score: 5
Accepted
time: 2ms
memory: 11820kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 13792kb
Pretest #7:
score: 5
Accepted
time: 2ms
memory: 11764kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 11888kb
Pretest #9:
score: 5
Accepted
time: 4ms
memory: 13880kb
Pretest #10:
score: 5
Accepted
time: 4ms
memory: 11832kb
Pretest #11:
score: 5
Accepted
time: 21ms
memory: 17976kb
Pretest #12:
score: 5
Accepted
time: 18ms
memory: 17860kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 11748kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 11856kb
Pretest #15:
score: 5
Accepted
time: 24ms
memory: 19488kb
Pretest #16:
score: 5
Accepted
time: 33ms
memory: 20088kb
Pretest #17:
score: 5
Accepted
time: 3ms
memory: 11768kb
Pretest #18:
score: 5
Accepted
time: 5ms
memory: 14728kb
Pretest #19:
score: 5
Accepted
time: 43ms
memory: 20052kb
Pretest #20:
score: 5
Accepted
time: 57ms
memory: 28224kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 13864kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 11808kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 13932kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 11832kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 11768kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 13812kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 11808kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 11800kb
Test #9:
score: 5
Accepted
time: 8ms
memory: 13848kb
Test #10:
score: 5
Accepted
time: 4ms
memory: 15964kb
Test #11:
score: 5
Accepted
time: 17ms
memory: 17952kb
Test #12:
score: 5
Accepted
time: 14ms
memory: 18028kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 11760kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 13968kb
Test #15:
score: 5
Accepted
time: 31ms
memory: 18028kb
Test #16:
score: 5
Accepted
time: 24ms
memory: 18920kb
Test #17:
score: 5
Accepted
time: 0ms
memory: 11816kb
Test #18:
score: 5
Accepted
time: 5ms
memory: 14804kb
Test #19:
score: 5
Accepted
time: 54ms
memory: 19828kb
Test #20:
score: 5
Accepted
time: 52ms
memory: 28160kb
Extra Test:
score: 0
Extra Test Passed