QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#526400 | #9155. 集合 | bashkort# | 100 ✓ | 1044ms | 68844kb | C++20 | 2.3kb | 2024-08-21 15:23:31 | 2024-08-21 15:23:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ar = array<int, 3>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<ar> a(n), b(n);
for (int i = 0; i < n; ++i) {
for (auto &f : a[i]) {
cin >> f;
--f;
}
}
for (int i = 0; i < n; ++i) {
for (auto &f : b[i]) {
cin >> f;
--f;
}
}
struct Struct {
vector<int> cnt;
map<pair<int, int>, int> mp;
void init(int k) {
cnt.assign(k, 0);
}
void modify(ar a, ar b, int mod) {
for (int &x : a) {
cnt[x] += mod;
}
for (int x : a) {
for (int y : b) {
mp[{x, y}] += mod;
}
}
}
int check(ar a, ar b) {
ar adj{};
for (int i = 0; i < 3; ++i) {
int need = cnt[a[i]];
for (int j = 0; j < 3; ++j) {
if (mp[{a[i], b[j]}] == need) {
adj[i] |= 1 << j;
}
}
}
for (int mask = 1; mask < (1 << 3); ++mask) {
int now = 0;
for (int i = 0; i < 3; ++i) {
if (mask >> i & 1) {
now |= adj[i];
}
}
if (__builtin_popcount(mask) > __builtin_popcount(now)) {
return false;
}
}
return true;
}
} A, B;
A.init(m), B.init(m);
vector<int> mxr(n + 1, n);
for (int i = n - 1; i >= 0; --i) {
mxr[i] = mxr[i + 1];
A.modify(a[i], b[i], 1);
B.modify(b[i], a[i], 1);
while (mxr[i] > i && (!A.check(a[i], b[i]) || !B.check(b[i], a[i]))) {
mxr[i] -= 1;
A.modify(a[mxr[i]], b[mxr[i]], -1);
B.modify(b[mxr[i]], a[mxr[i]], -1);
}
}
while (q--) {
int l, r;
cin >> l >> r;
--l;
if (mxr[l] >= r) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 3604kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 3600kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 3624kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 3560kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 3596kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 3604kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 3540kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 3548kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 3632kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 3540kb
Pretest #11:
score: 5
Accepted
time: 195ms
memory: 8496kb
Pretest #12:
score: 5
Accepted
time: 230ms
memory: 8512kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 3704kb
Pretest #14:
score: 5
Accepted
time: 7ms
memory: 4352kb
Pretest #15:
score: 5
Accepted
time: 107ms
memory: 3592kb
Pretest #16:
score: 5
Accepted
time: 109ms
memory: 4180kb
Pretest #17:
score: 5
Accepted
time: 61ms
memory: 6076kb
Pretest #18:
score: 5
Accepted
time: 56ms
memory: 8880kb
Pretest #19:
score: 5
Accepted
time: 1044ms
memory: 39616kb
Pretest #20:
score: 5
Accepted
time: 987ms
memory: 68844kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 3540kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 3484kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 3820kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 3488kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 3548kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 3624kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 3828kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 3824kb
Test #9:
score: 5
Accepted
time: 19ms
memory: 3576kb
Test #10:
score: 5
Accepted
time: 19ms
memory: 3504kb
Test #11:
score: 5
Accepted
time: 201ms
memory: 8568kb
Test #12:
score: 5
Accepted
time: 230ms
memory: 8460kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 3636kb
Test #14:
score: 5
Accepted
time: 6ms
memory: 4028kb
Test #15:
score: 5
Accepted
time: 107ms
memory: 3896kb
Test #16:
score: 5
Accepted
time: 105ms
memory: 4172kb
Test #17:
score: 5
Accepted
time: 60ms
memory: 5908kb
Test #18:
score: 5
Accepted
time: 64ms
memory: 9392kb
Test #19:
score: 5
Accepted
time: 1021ms
memory: 35772kb
Test #20:
score: 5
Accepted
time: 1000ms
memory: 68240kb
Extra Test:
score: 0
Extra Test Passed