QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#506718 | #9155. 集合 | jijidawang | 100 ✓ | 182ms | 20176kb | C++20 | 2.0kb | 2024-08-05 20:53:48 | 2024-08-05 20:53:48 |
Judging History
answer
#include <bits/stdc++.h>
namespace // my guiding star
{
#define filein(x) freopen(x".in", "r", stdin);
#define fileout(x) freopen(x, "w", stdout);
#define fileerr(x) freopen(x, "w", stderr);
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
#define files(x) freopen(x".in", "r", stdin), freopen(x".ans", "w", stdout);
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
#undef cT
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef unsigned u32;
template <typename T>
using pr = pair<T, T>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd;
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts(x ? "Yes" : "No");}
}
const int N = 2e5 + 233;
int n, m, q, a[N][3], b[N][3], ans[N];
mt19937_64 rnd(1);
ull xorshift(ull x){x ^= 1 << 13; x ^= x >> 7; x ^= x << 17; return x;}
ull hshA, hshB, val[N], valA[N * 3], valB[N * 3];
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i=1; i<=n; i++) scanf("%d%d%d", a[i], a[i]+1, a[i]+2);
for (int i=1; i<=n; i++) scanf("%d%d%d", b[i], b[i]+1, b[i]+2);
for (int i=1; i<=n; i++) val[i] = rnd();
auto insert = [&](int p, int op)
{
for (int i=0; i<3; i++)
{
int x = a[p][i];
hshA -= xorshift(valA[x]); valA[x] += val[p] * op; hshA += xorshift(valA[x]);
x = b[p][i];
hshB -= xorshift(valB[x]); valB[x] += val[p] * op; hshB += xorshift(valB[x]);
}
};
for (int i=n, j=n; i>=1; i--)
{
insert(i, 1);
while (hshA != hshB) insert(j--, -1);
ans[i] = j;
}
int l, r;
while (q--){scanf("%d%d", &l, &r); YN(ans[l] >= r);}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 9892kb
Pretest #2:
score: 5
Accepted
time: 2ms
memory: 9832kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9908kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 9892kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 9964kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 9968kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 11808kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 9776kb
Pretest #9:
score: 5
Accepted
time: 14ms
memory: 9888kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 9772kb
Pretest #11:
score: 5
Accepted
time: 58ms
memory: 11004kb
Pretest #12:
score: 5
Accepted
time: 69ms
memory: 10912kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 9832kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 9920kb
Pretest #15:
score: 5
Accepted
time: 93ms
memory: 9964kb
Pretest #16:
score: 5
Accepted
time: 101ms
memory: 12024kb
Pretest #17:
score: 5
Accepted
time: 7ms
memory: 12012kb
Pretest #18:
score: 5
Accepted
time: 4ms
memory: 12952kb
Pretest #19:
score: 5
Accepted
time: 174ms
memory: 12204kb
Pretest #20:
score: 5
Accepted
time: 182ms
memory: 20176kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 9896kb
Test #2:
score: 5
Accepted
time: 2ms
memory: 9908kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9968kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9816kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9904kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 9788kb
Test #7:
score: 5
Accepted
time: 2ms
memory: 9968kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 9776kb
Test #9:
score: 5
Accepted
time: 21ms
memory: 9756kb
Test #10:
score: 5
Accepted
time: 17ms
memory: 11884kb
Test #11:
score: 5
Accepted
time: 61ms
memory: 12296kb
Test #12:
score: 5
Accepted
time: 61ms
memory: 12160kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 9884kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 9844kb
Test #15:
score: 5
Accepted
time: 104ms
memory: 9896kb
Test #16:
score: 5
Accepted
time: 105ms
memory: 9924kb
Test #17:
score: 5
Accepted
time: 7ms
memory: 9908kb
Test #18:
score: 5
Accepted
time: 8ms
memory: 10772kb
Test #19:
score: 5
Accepted
time: 169ms
memory: 11840kb
Test #20:
score: 5
Accepted
time: 171ms
memory: 20084kb
Extra Test:
score: 0
Extra Test Passed