QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#502486 | #9155. 集合 | Insert_Username_Here | 100 ✓ | 187ms | 20840kb | C++20 | 1.3kb | 2024-08-03 07:29:15 | 2024-08-03 07:29:15 |
Judging History
answer
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef array<int, 3> arr;
const ll mod = 1e9 + 7;
// cope counter = 2254
ll rng() {
static ll x = 123456789, y = 362436069, z = 521288629;
ll t;
x ^= x << 16, x ^= x >> 5, x ^= x << 1;
t = x, x = y, y = z, z = t ^ x ^ y;
return x ^ y ^ z;
}
const int N = 2e5 + 1;
arr a[N], b[N];
ll bk[N], ans[N], fa[3 * N], fb[3 * N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
for(int i = 0; i < n; i++) for(int j = 0; j < 3; j++) cin >> a[i][j];
for(int i = 0; i < n; i++) for(int j = 0; j < 3; j++) cin >> b[i][j];
for(int i = 0; i < n; i++) bk[i] = rng() % mod;
for(int i = 0; i <= 3 * n; i++) fa[i] = fb[i] = 0;
int j = 0, l, r;
int aa[3], bb[3];
for(int i = 0; i < n; i++) {
while(j < n) {
for(int k = 0; k < 3; k++) aa[k] = fa[a[j][k]], bb[k] = fb[b[j][k]];
sort(aa, aa + 3), sort(bb, bb + 3);
if(aa[0] != bb[0] || aa[1] != bb[1] || aa[2] != bb[2]) break;
for(int k = 0; k < 3; k++) fa[a[j][k]] ^= bk[j], fb[b[j][k]] ^= bk[j];
j++;
}
ans[i] = j;
for(int &k : a[i]) fa[k] ^= bk[i];
for(int &k : b[i]) fb[k] ^= bk[i];
}
for(int i = 0; i < q; i++) {
cin >> l >> r;
cout << (ans[l - 1] >= r ? "Yes\n" : "No\n");
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 2ms
memory: 13868kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 13848kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 13804kb
Pretest #4:
score: 5
Accepted
time: 2ms
memory: 13792kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 13852kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 13852kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 11824kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 13952kb
Pretest #9:
score: 5
Accepted
time: 15ms
memory: 13952kb
Pretest #10:
score: 5
Accepted
time: 16ms
memory: 11860kb
Pretest #11:
score: 5
Accepted
time: 62ms
memory: 20756kb
Pretest #12:
score: 5
Accepted
time: 70ms
memory: 20804kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 13912kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 13864kb
Pretest #15:
score: 5
Accepted
time: 95ms
memory: 13848kb
Pretest #16:
score: 5
Accepted
time: 92ms
memory: 11948kb
Pretest #17:
score: 5
Accepted
time: 4ms
memory: 16340kb
Pretest #18:
score: 5
Accepted
time: 4ms
memory: 16240kb
Pretest #19:
score: 5
Accepted
time: 170ms
memory: 20820kb
Pretest #20:
score: 5
Accepted
time: 187ms
memory: 20776kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 13880kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 13792kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 13808kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 11824kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 11764kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 13876kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 11816kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 13804kb
Test #9:
score: 5
Accepted
time: 20ms
memory: 11756kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 13956kb
Test #11:
score: 5
Accepted
time: 62ms
memory: 20836kb
Test #12:
score: 5
Accepted
time: 66ms
memory: 20808kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 11944kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 11880kb
Test #15:
score: 5
Accepted
time: 101ms
memory: 13976kb
Test #16:
score: 5
Accepted
time: 104ms
memory: 11800kb
Test #17:
score: 5
Accepted
time: 8ms
memory: 15864kb
Test #18:
score: 5
Accepted
time: 8ms
memory: 14392kb
Test #19:
score: 5
Accepted
time: 164ms
memory: 20832kb
Test #20:
score: 5
Accepted
time: 186ms
memory: 20840kb
Extra Test:
score: 0
Extra Test Passed