QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#505947 | #9155. 集合 | _HKSR_ | 100 ✓ | 570ms | 25716kb | C++14 | 1.8kb | 2024-08-05 13:57:47 | 2024-08-05 13:57:47 |
Judging History
answer
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <random>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <sstream>
#include <bitset>
#include <fstream>
#include <climits>
#include <time.h>
#include <cassert>
using namespace std;
#define int long long
#define double long double
#define endl "\n"
int n,m,q;
int a[200300][3],b[200300][3];
int sa[600200],sb[600300];
int w[200200];
mt19937_64 RD(time(0));
inline void fla(int v,int x){
sa[v]^=w[x];
}
inline void flb(int v,int x){
sb[v]^=w[x];
}
inline void flip(int x){
for(int i=0;i<3;i++)
fla(a[x][i],x),
flb(b[x][i],x);
}
inline bool chk(int x){
vector<int>A,B;
for(int i=0;i<3;i++)
A.push_back(sa[a[x][i]]);
for(int i=0;i<3;i++)
B.push_back(sb[b[x][i]]);
sort(A.begin(),A.end());
sort(B.begin(),B.end());
for(int i=0;i<3;i++)
if(A[i]!=B[i])return 0;
return 1;
}
int rlim[200300];
signed main(){
ios::sync_with_stdio(0);
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>m>>q;
for(int i=1;i<= n;i++)
w[i]=RD();
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];
int r=0;
for(int l=1;l<=n;l++){
while(r<n&&chk(r+1))flip(++r);
flip(l);
rlim[l]=r;
// cout<<l<<" "<<r<<endl;
}
while(q--){
int l,r;
cin>>l>>r;
if(rlim[l]>=r)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
fflush(stdout);
cout.flush();
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 9812kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 9820kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 10064kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 9836kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 7992kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9772kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 9884kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9836kb
Pretest #9:
score: 5
Accepted
time: 60ms
memory: 9764kb
Pretest #10:
score: 5
Accepted
time: 68ms
memory: 9844kb
Pretest #11:
score: 5
Accepted
time: 187ms
memory: 19424kb
Pretest #12:
score: 5
Accepted
time: 184ms
memory: 17368kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 8028kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 10132kb
Pretest #15:
score: 5
Accepted
time: 303ms
memory: 10092kb
Pretest #16:
score: 5
Accepted
time: 343ms
memory: 10080kb
Pretest #17:
score: 5
Accepted
time: 12ms
memory: 9972kb
Pretest #18:
score: 5
Accepted
time: 13ms
memory: 13212kb
Pretest #19:
score: 5
Accepted
time: 495ms
memory: 17384kb
Pretest #20:
score: 5
Accepted
time: 570ms
memory: 25512kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 9812kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 9836kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 7776kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 7884kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 7772kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 10024kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 9812kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 9824kb
Test #9:
score: 5
Accepted
time: 59ms
memory: 9768kb
Test #10:
score: 5
Accepted
time: 44ms
memory: 9972kb
Test #11:
score: 5
Accepted
time: 181ms
memory: 19412kb
Test #12:
score: 5
Accepted
time: 166ms
memory: 17432kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 9844kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 10152kb
Test #15:
score: 5
Accepted
time: 336ms
memory: 7804kb
Test #16:
score: 5
Accepted
time: 332ms
memory: 7856kb
Test #17:
score: 5
Accepted
time: 13ms
memory: 12040kb
Test #18:
score: 5
Accepted
time: 14ms
memory: 12956kb
Test #19:
score: 5
Accepted
time: 411ms
memory: 17392kb
Test #20:
score: 5
Accepted
time: 444ms
memory: 25716kb
Extra Test:
score: 0
Extra Test Passed