QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#496503 | #9155. 集合 | Tx_Lcy# | 100 ✓ | 181ms | 25536kb | C++14 | 1.2kb | 2024-07-28 11:47:48 | 2024-07-28 11:47:48 |
Judging History
answer
//A tree without skin will surely die.
//A man without face will be alive.
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define all(x) (x).begin(),(x).end()
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define per(i,j,k) for (int i=j;i>=k;--i)
int const N=6e5+10;
int n,m,q,mx[N],a[N][3],b[N][3];
mt19937_64 rnd(time(0));
ull t1[N],t2[N],sm1,sm2,rnd1[N];
inline void add(int id){
rep(j,0,2)
sm1-=t1[a[id][j]],t1[a[id][j]]^=rnd1[id],sm1+=t1[a[id][j]],
sm2-=t2[b[id][j]],t2[b[id][j]]^=rnd1[id],sm2+=t2[b[id][j]];
}
inline void solve(){
cin>>n>>m>>q;
rep(i,1,n) cin>>a[i][0]>>a[i][1]>>a[i][2];
rep(i,1,n) cin>>b[i][0]>>b[i][1]>>b[i][2];
rep(i,1,n) rnd1[i]=rnd();
int j=0;
rep(i,1,n){
while (j+1<=n){
++j,add(j);
if (sm1!=sm2){add(j),--j;break;}
}
mx[i]=j,add(i);
}
rep(i,1,q){
int l,r;cin>>l>>r;
if (mx[l]>=r) cout<<"Yes\n";
else cout<<"No\n";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t=1;
// cin>>t;
while (t--) solve();
cerr<<"Time: "<<(double)clock()/CLOCKS_PER_SEC<<" s\n";
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 10096kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 10092kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 10136kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 9900kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 10080kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 10120kb
Pretest #7:
score: 5
Accepted
time: 2ms
memory: 10100kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 9996kb
Pretest #9:
score: 5
Accepted
time: 16ms
memory: 10056kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 10128kb
Pretest #11:
score: 5
Accepted
time: 62ms
memory: 18028kb
Pretest #12:
score: 5
Accepted
time: 54ms
memory: 17592kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 10052kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 10196kb
Pretest #15:
score: 5
Accepted
time: 100ms
memory: 10136kb
Pretest #16:
score: 5
Accepted
time: 102ms
memory: 10248kb
Pretest #17:
score: 5
Accepted
time: 6ms
memory: 10256kb
Pretest #18:
score: 5
Accepted
time: 8ms
memory: 13232kb
Pretest #19:
score: 5
Accepted
time: 164ms
memory: 16688kb
Pretest #20:
score: 5
Accepted
time: 172ms
memory: 25536kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 10100kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 10080kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 10096kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 10080kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 10088kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 10096kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 10036kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 10088kb
Test #9:
score: 5
Accepted
time: 16ms
memory: 10104kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 10032kb
Test #11:
score: 5
Accepted
time: 54ms
memory: 19828kb
Test #12:
score: 5
Accepted
time: 64ms
memory: 17808kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 10116kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 12276kb
Test #15:
score: 5
Accepted
time: 104ms
memory: 9916kb
Test #16:
score: 5
Accepted
time: 101ms
memory: 10196kb
Test #17:
score: 5
Accepted
time: 6ms
memory: 10256kb
Test #18:
score: 5
Accepted
time: 3ms
memory: 11216kb
Test #19:
score: 5
Accepted
time: 172ms
memory: 16504kb
Test #20:
score: 5
Accepted
time: 181ms
memory: 24816kb
Extra Test:
score: 0
Extra Test Passed