QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498637 | #9155. 集合 | CuFeO4 | 100 ✓ | 367ms | 65552kb | C++14 | 1.6kb | 2024-07-30 17:03:57 | 2024-07-30 17:03:58 |
Judging History
answer
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
bool StdIn = cin.tie(nullptr)->sync_with_stdio(false);
bool StdOut = cout.tie(nullptr)->sync_with_stdio(false);
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 6e5 + 10;
int n,m,q;
int a[N][4],b[N][4],tot,p[N];
ull A[N],B[N],rd[N];
mt19937_64 rnd(time(NULL));
unordered_map<ull,int> cnt;
inline void insert(ull x,int opt){
if(cnt[x] != 0) tot--;
if((cnt[x]+=opt)!=0) tot++;
}
inline void work(int i){
for(int j = 1;j <= 3; ++j){
insert(A[a[i][j]],-1),A[a[i][j]]^=rd[i],insert(A[a[i][j]],1);
insert(B[b[i][j]],1),B[b[i][j]]^=rd[i],insert(B[b[i][j]],-1);
}
}
signed main(){
cin>>n>>m>>q;
for(int i = 1;i <= n; ++i) for(int j = 1;j <= 3; ++j) cin>>a[i][j];
for(int i = 1;i <= n; ++i) for(int j = 1;j <= 3; ++j) cin>>b[i][j];
for(int i = 1;i <= n; ++i) rd[i] = rnd();
for(int l = 1,r = 0;l <= n; ++l){
while(r <= n && tot == 0) work(++r);
p[l] = r;
work(l);
}
while(q--){
int l,r;cin>>l>>r;
cout<<(p[l]>r?"Yes\n":"No\n");
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 9828kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 9976kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 10040kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 10040kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 10052kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9780kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 9832kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 10088kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 9868kb
Pretest #10:
score: 5
Accepted
time: 16ms
memory: 9884kb
Pretest #11:
score: 5
Accepted
time: 268ms
memory: 64772kb
Pretest #12:
score: 5
Accepted
time: 260ms
memory: 62488kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 10236kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 10208kb
Pretest #15:
score: 5
Accepted
time: 102ms
memory: 10256kb
Pretest #16:
score: 5
Accepted
time: 90ms
memory: 12352kb
Pretest #17:
score: 5
Accepted
time: 18ms
memory: 14204kb
Pretest #18:
score: 5
Accepted
time: 14ms
memory: 15172kb
Pretest #19:
score: 5
Accepted
time: 367ms
memory: 61608kb
Pretest #20:
score: 5
Accepted
time: 361ms
memory: 64840kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 10040kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 9820kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 9820kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 9840kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9820kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9776kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 10092kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 9860kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 10100kb
Test #10:
score: 5
Accepted
time: 17ms
memory: 9884kb
Test #11:
score: 5
Accepted
time: 259ms
memory: 61052kb
Test #12:
score: 5
Accepted
time: 242ms
memory: 59952kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 12228kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 10496kb
Test #15:
score: 5
Accepted
time: 97ms
memory: 10252kb
Test #16:
score: 5
Accepted
time: 102ms
memory: 10512kb
Test #17:
score: 5
Accepted
time: 19ms
memory: 14364kb
Test #18:
score: 5
Accepted
time: 23ms
memory: 15292kb
Test #19:
score: 5
Accepted
time: 363ms
memory: 61276kb
Test #20:
score: 5
Accepted
time: 361ms
memory: 65552kb
Extra Test:
score: 0
Extra Test Passed