QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490633 | #9155. 集合 | c20230201 | 100 ✓ | 288ms | 20096kb | C++14 | 1.2kb | 2024-07-25 15:55:59 | 2024-07-25 15:56:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e5+5, maxm=6e5+5;
int a[maxn][3], b[maxn][3], L[maxn];
ull f[maxm], g[maxm], v[maxn];
unordered_map<ull,int> mp;
ull random_x() {
return 1ull*rand()*rand()*rand()*rand();
}
void add(int i,int o) {
for(int j=0;j<3;j++) {
mp[f[a[i][j]]]--;
if(mp[f[a[i][j]]]==0) mp.erase(f[a[i][j]]);
mp[g[b[i][j]]]++;
if(mp[g[b[i][j]]]==0) mp.erase(g[b[i][j]]);
f[a[i][j]]+= o*v[i];
g[b[i][j]]+= o*v[i];
mp[f[a[i][j]]]++;
if(mp[f[a[i][j]]]==0) mp.erase(f[a[i][j]]);
mp[g[b[i][j]]]--;
if(mp[g[b[i][j]]]==0) mp.erase(g[b[i][j]]);
}
return ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
srand(time(0));
int n,m,q; cin>>n>>m>>q;
for(int i=1;i<=n;i++) v[i]=random_x();
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 l=1;
for(int i=1;i<=n;i++) {
add(i,1);
while(l<=i&&mp.size()) add(l++,-1);
L[i]=l;
}
for(int i=1;i<=q;i++) {
int l,r; cin>>l>>r;
if(L[r]<=l) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 7700kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 9812kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9796kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 7808kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 7768kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 7916kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 7984kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 9744kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 7768kb
Pretest #10:
score: 5
Accepted
time: 17ms
memory: 7928kb
Pretest #11:
score: 5
Accepted
time: 172ms
memory: 11648kb
Pretest #12:
score: 5
Accepted
time: 173ms
memory: 11836kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 9828kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 9988kb
Pretest #15:
score: 5
Accepted
time: 97ms
memory: 9848kb
Pretest #16:
score: 5
Accepted
time: 97ms
memory: 9920kb
Pretest #17:
score: 5
Accepted
time: 18ms
memory: 7992kb
Pretest #18:
score: 5
Accepted
time: 19ms
memory: 10856kb
Pretest #19:
score: 5
Accepted
time: 288ms
memory: 14168kb
Pretest #20:
score: 5
Accepted
time: 284ms
memory: 20068kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 7756kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 7756kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9756kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 10032kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9968kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 7760kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 7992kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 8016kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 8024kb
Test #10:
score: 5
Accepted
time: 19ms
memory: 7720kb
Test #11:
score: 5
Accepted
time: 169ms
memory: 11832kb
Test #12:
score: 5
Accepted
time: 167ms
memory: 12108kb
Test #13:
score: 5
Accepted
time: 3ms
memory: 10080kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 7896kb
Test #15:
score: 5
Accepted
time: 105ms
memory: 10084kb
Test #16:
score: 5
Accepted
time: 102ms
memory: 9928kb
Test #17:
score: 5
Accepted
time: 18ms
memory: 7932kb
Test #18:
score: 5
Accepted
time: 18ms
memory: 8840kb
Test #19:
score: 5
Accepted
time: 283ms
memory: 11732kb
Test #20:
score: 5
Accepted
time: 282ms
memory: 20096kb
Extra Test:
score: 0
Extra Test Passed