QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498880 | #9155. 集合 | Floze3 | 100 ✓ | 182ms | 20100kb | C++17 | 2.9kb | 2024-07-30 20:58:38 | 2024-07-30 20:58:40 |
Judging History
answer
// Author: Floze3
// Time: 2024-07-30 20:34:33
// Problem: P10785 [NOI2024] 集合
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10785
// Memory Limit: MB
// Time Limit: ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define mp(x, y) std::make_pair(x, y)
#define eb emplace_back
#define fi first
#define se second
#define il inline
#define all(x) x.begin(), x.end()
#define file(name) \
freopen(name ".in", "r", stdin); \
freopen(name ".out", "w", stdout);
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
#ifndef ONLINE_JUDGE
#define debug(x) \
std::cerr << "In Line " << __LINE__ << ": " << #x << " = " << x << std::endl
#define look_time std::cerr << clock() * 1e3 / CLOCKS_PER_SEC << " ms\n"
#define look_memory std::cerr << fabs(&med - &mst) / 1024.0 / 1024.0 << " mb\n"
#else
#define debug(...) 42
#define look_time 42
#define look_memory 42
#endif
const int N = 2e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
std::mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());
bool mst;
const ull msk = rng();
ull sa, sb, ap[N * 3], bp[N * 3], mp[N];
int n, m, q, rm[N], a[N][3], b[N][3];
il ull sft(ull x) {
if (!x) return x;
x ^= msk;
x ^= x << 7;
x ^= x >> 11;
x ^= x << 13;
return x;
}
il void del(int pos) {
for (int i = 0; i < 3; ++i) {
sa -= sft(ap[a[pos][i]]);
ap[a[pos][i]] -= mp[pos];
sa += sft(ap[a[pos][i]]);
}
for (int i = 0; i < 3; ++i) {
sb -= sft(bp[b[pos][i]]);
bp[b[pos][i]] -= mp[pos];
sb += sft(bp[b[pos][i]]);
}
return ;
}
il void add(int pos) {
for (int i = 0; i < 3; ++i) {
sa -= sft(ap[a[pos][i]]);
ap[a[pos][i]] += mp[pos];
sa += sft(ap[a[pos][i]]);
}
for (int i = 0; i < 3; ++i) {
sb -= sft(bp[b[pos][i]]);
bp[b[pos][i]] += mp[pos];
sb += sft(bp[b[pos][i]]);
}
return ;
}
bool med;
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 3; ++j) std::cin >> a[i][j];
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 3; ++j) std::cin >> b[i][j];
}
for (int i = 1; i <= n; ++i) mp[i] = rng();
for (int i = 1; i <= n; ++i) rm[i] = n;
add(1);
for (int i = 1, j = 1; i <= n; del(i++)) {
while (j <= n && sa == sb) {
++j;
if (j <= n) add(j);
}
rm[i] = std::min(rm[i], j - 1);
}
// for (int i = 1; i <= n; ++i) std::cout << i << ' ' << rm[i] << '\n';
while (q--) {
int l, r;
std::cin >> l >> r;
std::cout << (r <= rm[l] ? "Yes\n" : "No\n");
}
return 0;
}
/*
all the things you do
the words you say
will all come back to you
*/
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 7672kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 7804kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 7804kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 7664kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 9852kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 7816kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 7752kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 7688kb
Pretest #9:
score: 5
Accepted
time: 19ms
memory: 7704kb
Pretest #10:
score: 5
Accepted
time: 19ms
memory: 7816kb
Pretest #11:
score: 5
Accepted
time: 63ms
memory: 11116kb
Pretest #12:
score: 5
Accepted
time: 59ms
memory: 10988kb
Pretest #13:
score: 5
Accepted
time: 1ms
memory: 7840kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 7932kb
Pretest #15:
score: 5
Accepted
time: 98ms
memory: 7760kb
Pretest #16:
score: 5
Accepted
time: 104ms
memory: 7788kb
Pretest #17:
score: 5
Accepted
time: 6ms
memory: 8100kb
Pretest #18:
score: 5
Accepted
time: 8ms
memory: 10912kb
Pretest #19:
score: 5
Accepted
time: 167ms
memory: 11704kb
Pretest #20:
score: 5
Accepted
time: 182ms
memory: 20100kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 7812kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 7736kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 7820kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 9720kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9784kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 9784kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 9864kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 7740kb
Test #9:
score: 5
Accepted
time: 19ms
memory: 7744kb
Test #10:
score: 5
Accepted
time: 15ms
memory: 7772kb
Test #11:
score: 5
Accepted
time: 56ms
memory: 11812kb
Test #12:
score: 5
Accepted
time: 64ms
memory: 10880kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 9836kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 9984kb
Test #15:
score: 5
Accepted
time: 98ms
memory: 7828kb
Test #16:
score: 5
Accepted
time: 96ms
memory: 7936kb
Test #17:
score: 5
Accepted
time: 3ms
memory: 10012kb
Test #18:
score: 5
Accepted
time: 4ms
memory: 10968kb
Test #19:
score: 5
Accepted
time: 162ms
memory: 12108kb
Test #20:
score: 5
Accepted
time: 174ms
memory: 19968kb
Extra Test:
score: 0
Extra Test Passed