QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#537295 | #9155. 集合 | shiomusubi496# | 100 ✓ | 199ms | 19696kb | C++17 | 2.0kb | 2024-08-30 09:23:40 | 2024-08-30 09:23:41 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
constexpr ll inf = 1001001001001001001;
mt19937_64 mt(random_device{}());
int main() {
int N, M, Q; scanf("%d%d%d", &N, &M, &Q);
vector<array<int, 3>> A(N), B(N);
rep (i, N) rep (j, 3) scanf("%d", &A[i][j]), --A[i][j];
rep (i, N) rep (j, 3) scanf("%d", &B[i][j]), --B[i][j];
vector<ull> X(N);
rep (i, N) X[i] = mt();
vector<int> R(N);
int cur = 0;
vector<ull> YA(M), YB(M);
ull ZA = 0, ZB = 0;
auto check = [&] {
ull nxt_za = ZA, nxt_zb = ZB;
rep (i, 3) nxt_za += (YA[A[cur][i]] ^ X[cur]) - YA[A[cur][i]];
rep (i, 3) nxt_zb += (YB[B[cur][i]] ^ X[cur]) - YB[B[cur][i]];
return nxt_za == nxt_zb;
};
rep (l, N) {
while (cur < N && check()) {
rep (i, 3) ZA += (YA[A[cur][i]] ^ X[cur]) - YA[A[cur][i]];
rep (i, 3) ZB += (YB[B[cur][i]] ^ X[cur]) - YB[B[cur][i]];
rep (i, 3) YA[A[cur][i]] ^= X[cur];
rep (i, 3) YB[B[cur][i]] ^= X[cur];
++cur;
}
R[l] = cur;
rep (i, 3) ZA += (YA[A[l][i]] ^ X[l]) - YA[A[l][i]];
rep (i, 3) ZB += (YB[B[l][i]] ^ X[l]) - YB[B[l][i]];
rep (i, 3) YA[A[l][i]] ^= X[l];
rep (i, 3) YB[B[l][i]] ^= X[l];
}
rep (_, Q) {
int l, r; scanf("%d%d", &l, &r);
--l;
puts(R[l] >= r ? "Yes" : "No");
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 3680kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 3692kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 3988kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 3692kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 3720kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 3700kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 3664kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 3760kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 3760kb
Pretest #10:
score: 5
Accepted
time: 20ms
memory: 3712kb
Pretest #11:
score: 5
Accepted
time: 78ms
memory: 10344kb
Pretest #12:
score: 5
Accepted
time: 78ms
memory: 10264kb
Pretest #13:
score: 5
Accepted
time: 1ms
memory: 3688kb
Pretest #14:
score: 5
Accepted
time: 1ms
memory: 4144kb
Pretest #15:
score: 5
Accepted
time: 99ms
memory: 3688kb
Pretest #16:
score: 5
Accepted
time: 115ms
memory: 3848kb
Pretest #17:
score: 5
Accepted
time: 6ms
memory: 4104kb
Pretest #18:
score: 5
Accepted
time: 8ms
memory: 4916kb
Pretest #19:
score: 5
Accepted
time: 182ms
memory: 10244kb
Pretest #20:
score: 5
Accepted
time: 199ms
memory: 19616kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 3708kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 3656kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 3640kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 3760kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 3932kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 3684kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 3708kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 3956kb
Test #9:
score: 5
Accepted
time: 17ms
memory: 3644kb
Test #10:
score: 5
Accepted
time: 20ms
memory: 3960kb
Test #11:
score: 5
Accepted
time: 78ms
memory: 10440kb
Test #12:
score: 5
Accepted
time: 77ms
memory: 10244kb
Test #13:
score: 5
Accepted
time: 1ms
memory: 4052kb
Test #14:
score: 5
Accepted
time: 1ms
memory: 4152kb
Test #15:
score: 5
Accepted
time: 105ms
memory: 3760kb
Test #16:
score: 5
Accepted
time: 102ms
memory: 3788kb
Test #17:
score: 5
Accepted
time: 7ms
memory: 3892kb
Test #18:
score: 5
Accepted
time: 8ms
memory: 4980kb
Test #19:
score: 5
Accepted
time: 184ms
memory: 10340kb
Test #20:
score: 5
Accepted
time: 189ms
memory: 19696kb
Extra Test:
score: 0
Extra Test Passed