QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492079 | #9155. 集合 | Dawnq# | 100 ✓ | 477ms | 20188kb | C++14 | 1.3kb | 2024-07-26 09:04:51 | 2024-07-26 09:04:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N=2e5+5;
int n,m,q,a[N][3],b[N][3],R[N];
ull s1,s2,val,d[N],A[N*3],B[N*3];
mt19937_64 rnd(time(0));
inline ull calc(ull x){return x<<=5,x>>=7,x^=val,x<<=3,x>>=11;}
inline void add(int x){
if(x>n)return;
for(int i:a[x])s1-=calc(A[i]),A[i]+=d[x],s1+=calc(A[i]);
for(int i:b[x])s2-=calc(B[i]),B[i]+=d[x],s2+=calc(B[i]);
}
inline void del(int x){
if(x>n)return;
for(int i:a[x])s1-=calc(A[i]),A[i]-=d[x],s1+=calc(A[i]);
for(int i:b[x])s2-=calc(B[i]),B[i]-=d[x],s2+=calc(B[i]);
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
std::ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;++i){
for(int j=0;j<3;++j)cin>>a[i][j];
}
for(int i=1;i<=n;++i){
for(int j=0;j<3;++j)cin>>b[i][j];
}
for(int i=1;i<=n;++i)R[i]=n;
for(int op=1;op<=50;++op){
val=rnd(),s1=s2=0;
for(int i=1;i<=n;++i)d[i]=rnd(),A[i]=B[i]=0;
add(1);
for(int i=1,j=1;i<=n;++i){
while(j<=n&&s1==s2)++j,add(j);
R[i]=min(R[i],j-1),del(i);
}
}
while(q--){
int l,r;
cin>>l>>r;
if(R[l]>=r)cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 14004kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 11960kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 11876kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 13864kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 11876kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 11972kb
Pretest #7:
score: 5
Accepted
time: 2ms
memory: 12020kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 11880kb
Pretest #9:
score: 5
Accepted
time: 16ms
memory: 11884kb
Pretest #10:
score: 5
Accepted
time: 24ms
memory: 12016kb
Pretest #11:
score: 5
Accepted
time: 306ms
memory: 17992kb
Pretest #12:
score: 5
Accepted
time: 284ms
memory: 20184kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 11988kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 11932kb
Pretest #15:
score: 5
Accepted
time: 107ms
memory: 11900kb
Pretest #16:
score: 5
Accepted
time: 100ms
memory: 12020kb
Pretest #17:
score: 5
Accepted
time: 29ms
memory: 14080kb
Pretest #18:
score: 5
Accepted
time: 32ms
memory: 12440kb
Pretest #19:
score: 5
Accepted
time: 385ms
memory: 16096kb
Pretest #20:
score: 5
Accepted
time: 472ms
memory: 20032kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 11948kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 11952kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 11896kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 11900kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 11948kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 11900kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 11824kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 11876kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 11972kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 11964kb
Test #11:
score: 5
Accepted
time: 312ms
memory: 18124kb
Test #12:
score: 5
Accepted
time: 293ms
memory: 16084kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 11892kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 11892kb
Test #15:
score: 5
Accepted
time: 94ms
memory: 11900kb
Test #16:
score: 5
Accepted
time: 103ms
memory: 13904kb
Test #17:
score: 5
Accepted
time: 29ms
memory: 14172kb
Test #18:
score: 5
Accepted
time: 32ms
memory: 12440kb
Test #19:
score: 5
Accepted
time: 384ms
memory: 20168kb
Test #20:
score: 5
Accepted
time: 477ms
memory: 20188kb
Extra Test:
score: 0
Extra Test Passed