QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#490010 | #9155. 集合 | Ender32k | 100 ✓ | 426ms | 61592kb | C++14 | 1.8kb | 2024-07-25 10:15:11 | 2024-07-25 10:15:12 |
Judging History
answer
// 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 eb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
bool Mbe;
mt19937 rnd(time(0));
const int N = 2e5 + 5;
const int M = 6e5 + 5;
int n, m, q, res[N];
int a[N][3], b[N][3];
ull f[N], pa[M], pb[M], A, B;
unordered_map<ull, ull> h;
ull myr() {
return ((ull)rnd() << 32) + rnd();
}
ull g(ull x) {
if (h.find(x) == h.end()) h[x] = myr();
return h[x];
}
void add(int x, ull op) {
for (int i = 0; i <= 2; i++) {
A -= g(pa[a[x][i]]), B -= g(pb[b[x][i]]);
pa[a[x][i]] += f[x] * op;
pb[b[x][i]] += f[x] * op;
A += g(pa[a[x][i]]), B += g(pb[b[x][i]]);
}
}
void solve() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
cin >> a[i][0] >> a[i][1] >> a[i][2];
for (int i = 1; i <= n; i++)
cin >> b[i][0] >> b[i][1] >> b[i][2];
for (int i = 1; i <= n; i++) f[i] = myr();
for (int i = 1, j = 0; i <= n; i++) {
while (j + 1 <= n && (A == B)) add(++j, 1);
if (A != B) add(j--, -1);
res[i] = j, add(i, -1);
}
while (q--) {
int l, r; cin >> l >> r;
if (res[l] >= r) cout << "Yes\n";
else cout << "No\n";
}
}
bool Med;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
int T = 1;
// cin >> T;
while (T--) solve();
cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
return 0;
}
詳細信息
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 8040kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 10092kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 10084kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 7996kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 12096kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 10092kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 10072kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 8100kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 8032kb
Pretest #10:
score: 5
Accepted
time: 21ms
memory: 12232kb
Pretest #11:
score: 5
Accepted
time: 311ms
memory: 61592kb
Pretest #12:
score: 5
Accepted
time: 270ms
memory: 56716kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 12392kb
Pretest #14:
score: 5
Accepted
time: 3ms
memory: 10588kb
Pretest #15:
score: 5
Accepted
time: 107ms
memory: 8440kb
Pretest #16:
score: 5
Accepted
time: 105ms
memory: 12468kb
Pretest #17:
score: 5
Accepted
time: 26ms
memory: 16604kb
Pretest #18:
score: 5
Accepted
time: 19ms
memory: 17380kb
Pretest #19:
score: 5
Accepted
time: 426ms
memory: 56580kb
Pretest #20:
score: 5
Accepted
time: 408ms
memory: 60588kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 7976kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 12196kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 12312kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 12292kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 8000kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 10084kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 8000kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 12188kb
Test #9:
score: 5
Accepted
time: 16ms
memory: 10140kb
Test #10:
score: 5
Accepted
time: 16ms
memory: 12340kb
Test #11:
score: 5
Accepted
time: 304ms
memory: 57492kb
Test #12:
score: 5
Accepted
time: 285ms
memory: 56308kb
Test #13:
score: 5
Accepted
time: 4ms
memory: 10512kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 12504kb
Test #15:
score: 5
Accepted
time: 103ms
memory: 8400kb
Test #16:
score: 5
Accepted
time: 107ms
memory: 10432kb
Test #17:
score: 5
Accepted
time: 27ms
memory: 16604kb
Test #18:
score: 5
Accepted
time: 18ms
memory: 17516kb
Test #19:
score: 5
Accepted
time: 400ms
memory: 54816kb
Test #20:
score: 5
Accepted
time: 409ms
memory: 60924kb
Extra Test:
score: 0
Extra Test Passed