QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#490062 | #9155. 集合 | wxqwq | 100 ✓ | 112ms | 34140kb | C++14 | 2.1kb | 2024-07-25 10:56:41 | 2024-07-25 10:56:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0;bool f=0;char ch=getchar();
while(ch<'0' || ch>'9') {if(ch=='-') f=1;ch=getchar();}
while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return f?-x:x;
}
#define x first
#define y second
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ull;
const int N=2e5+10,M=6e5+10;
const ull P=998244853;
int n,m,q;
ull pa[N*3],pb[N*3],w[N];
int a[N][3],b[N][3];
int pre[N*3],lst[M],prb[N*3],lsb[M];
int psa[M],psb[M];
int R[N];
ull myrd() {
ull x=rand()*1llu*rand();
x^=x<<23,x|=x<<17,x^=x>>13;
return x;
}
int main()
{
n=read(),m=read(),q=read();//,srand(time(NULL));
for(int i=1;i<=n;i++) w[i]=myrd();
// rep(i,1,n) cout<<w[i]<<endl;
for(int i=1,o=1,x;i<=n;i++,o+=3) rep(j,0,2) {
x=read(),pre[o+j]=lst[x],a[i][j]=x;
pa[o+j]=pa[lst[x]]^w[i],lst[x]=o+j;
} for(int i=1,o=1,x;i<=n;i++,o+=3) rep(j,0,2) {
x=read(),prb[o+j]=lsb[x],b[i][j]=x;
pb[o+j]=pb[lsb[x]]^w[i],lsb[x]=o+j;
}
rep(i,1,m) psa[i]=lst[i],psb[i]=lsb[i];
R[n+1]=n;
// cout<<(pa[4]^pa[10])<<endl;
for(int i=n,o=n*3-2;i>=1;i--,o-=3) {
rep(j,0,2) while(psa[a[i][j]]>=o) psa[a[i][j]]=pre[psa[a[i][j]]];
rep(j,0,2) while(psb[b[i][j]]>=o) psb[b[i][j]]=prb[psb[b[i][j]]];
int r=R[i+1];
for(;r>i;r--) {
rep(j,0,2) while(lst[a[i][j]]>r*3) lst[a[i][j]]=pre[lst[a[i][j]]];
rep(j,0,2) while(lsb[b[i][j]]>r*3) lsb[b[i][j]]=prb[lsb[b[i][j]]];
ull sa[3]={0,0,0},sb[3]={0,0,0};
rep(j,0,2) {
sa[j]=pa[lst[a[i][j]]]^pa[psa[a[i][j]]];
sb[j]=pb[lsb[b[i][j]]]^pb[psb[b[i][j]]];
}
// rep(j,0,2) cout<<sa[j]<<' '<<sb[j]<<' '<<lst[a[i][j]]<<' '<<psa[a[i][j]]<<endl;
sort(sa,sa+3),sort(sb,sb+3); bool ok=1;
rep(j,0,2) ok&=(sa[j]==sb[j]);
if(ok) break;
}
// rep(j,1,m) cout<<lst[j]<<' '; puts("");
R[i]=r;
// cout<<i<<' '<<R[i]<<' '<<r<<endl;
}
int l,r;
while(q--) {
l=read(),r=read();
if(R[l]>=r) puts("Yes");
else puts("No");
}
return 0;
}
詳細信息
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 15868kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 17912kb
Pretest #3:
score: 5
Accepted
time: 2ms
memory: 15928kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 15844kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 15912kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 17948kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 15904kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 16004kb
Pretest #9:
score: 5
Accepted
time: 10ms
memory: 15880kb
Pretest #10:
score: 5
Accepted
time: 7ms
memory: 15940kb
Pretest #11:
score: 5
Accepted
time: 37ms
memory: 31500kb
Pretest #12:
score: 5
Accepted
time: 43ms
memory: 28760kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 18148kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 16152kb
Pretest #15:
score: 5
Accepted
time: 48ms
memory: 15916kb
Pretest #16:
score: 5
Accepted
time: 49ms
memory: 18036kb
Pretest #17:
score: 5
Accepted
time: 3ms
memory: 20616kb
Pretest #18:
score: 5
Accepted
time: 8ms
memory: 19388kb
Pretest #19:
score: 5
Accepted
time: 106ms
memory: 27552kb
Pretest #20:
score: 5
Accepted
time: 99ms
memory: 34140kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 15920kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 15908kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 15908kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 15904kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 15924kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 17984kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 17904kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 15932kb
Test #9:
score: 5
Accepted
time: 11ms
memory: 15848kb
Test #10:
score: 5
Accepted
time: 7ms
memory: 15936kb
Test #11:
score: 5
Accepted
time: 41ms
memory: 28000kb
Test #12:
score: 5
Accepted
time: 49ms
memory: 31592kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 18024kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 16096kb
Test #15:
score: 5
Accepted
time: 47ms
memory: 16044kb
Test #16:
score: 5
Accepted
time: 42ms
memory: 16132kb
Test #17:
score: 5
Accepted
time: 7ms
memory: 18940kb
Test #18:
score: 5
Accepted
time: 0ms
memory: 19596kb
Test #19:
score: 5
Accepted
time: 112ms
memory: 28800kb
Test #20:
score: 5
Accepted
time: 107ms
memory: 34080kb
Extra Test:
score: 0
Extra Test Passed