QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#693886 | #9155. 集合 | Qwerty1232 | 100 ✓ | 401ms | 190972kb | C++23 | 3.5kb | 2024-10-31 16:55:06 | 2024-10-31 16:55:10 |
Judging History
answer
// https://admin.contest.yandex.ru/submissions/123152263
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long long ll;
typedef long double ld;
struct SparseTable {
vector<int> a;
vector<vector<int>> spmin;
SparseTable() {}
void build(vector<int> c) {
a = c;
int n = a.size();
int log2n = log2(n) + 1;
spmin.resize(log2n, vector<int>(n));
for (int i = 0; i < n; ++i) spmin[0][i] = i;
for (int i = 1; i < log2n; ++i) {
for (int j = 0; j < n; ++j) {
int t = min(j + (1<<(i-1)), n - 1);
if (a[spmin[i - 1][j]] < a[spmin[i - 1][t]]) spmin[i][j] = spmin[i - 1][j];
else spmin[i][j] = spmin[i - 1][t];
}
}
}
int min_ind(int l, int r) {
int lg2 = log2(r - l + 1);
r++;
if (a[spmin[lg2][l]] < a[spmin[lg2][r - (1<<lg2)]]) return spmin[lg2][l];
return spmin[lg2][r - (1<<lg2)];
}
int get_min(int l, int r) {
int lg2 = log2(r - l + 1);
r++;
if (a[spmin[lg2][l]] < a[spmin[lg2][r - (1<<lg2)]]) return a[spmin[lg2][l]];
return a[spmin[lg2][r - (1<<lg2)]];
}
};
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> a(n, vector<int>(3)), b(n, vector<int>(3));
for (int i = 0; i < n; ++i) cin >> a[i][0] >> a[i][1] >> a[i][2];
for (int i = 0; i < n; ++i) cin >> b[i][0] >> b[i][1] >> b[i][2];
vector<int> fucked(n, -1);
vector<int> lasta(m + 1, n), lastb(m + 1, n);
vector<map<pair<int, int>, int>> lolkek(n);
for (int i = n - 1; i >= 0; --i) {
for (auto e : a[i]) {
for (auto x : b[i]) {
if (lasta[e] == lastb[x]) {
if (lasta[e] == n) {
lolkek[i][{e, x}] = n;
continue;
}
lolkek[i][{e, x}] = lolkek[lasta[e]][{e, x}];
continue;
}
lolkek[i][{e, x}] = min(lasta[e], lastb[x]);
}
}
for (auto e : a[i]) lasta[e] = i;
for (auto e : b[i]) lastb[e] = i;
vector<int> ord = {0, 1, 2};
do {
int X = n;
for (int j = 0; j < 3; ++j) {
X = min(X, lolkek[i][{a[i][j], b[i][ord[j]]}]);
}
fucked[i] = max(fucked[i], X);
} while (next_permutation(all(ord)));
}
// for (auto e : fucked) cout << e << ' '; cout << '\n';
SparseTable lol;
lol.build(fucked);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
--l;
if (lol.get_min(l, r - 1) >= r) cout << "Yes\n";
else cout << "No\n";
}
}
signed main() {
int tc = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#endif
// cin >> tc;
for (int t = 1; t <= tc; t++) {
// cout << "Case #" << t << ": ";
solve();
}
}
详细
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 3908kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 3944kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 3952kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 3612kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 3668kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 3728kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 3872kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 3852kb
Pretest #9:
score: 5
Accepted
time: 22ms
memory: 3872kb
Pretest #10:
score: 5
Accepted
time: 23ms
memory: 3740kb
Pretest #11:
score: 5
Accepted
time: 218ms
memory: 181660kb
Pretest #12:
score: 5
Accepted
time: 206ms
memory: 181416kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 5476kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 5316kb
Pretest #15:
score: 5
Accepted
time: 125ms
memory: 5412kb
Pretest #16:
score: 5
Accepted
time: 129ms
memory: 5384kb
Pretest #17:
score: 5
Accepted
time: 16ms
memory: 20560kb
Pretest #18:
score: 5
Accepted
time: 16ms
memory: 21564kb
Pretest #19:
score: 5
Accepted
time: 397ms
memory: 181480kb
Pretest #20:
score: 5
Accepted
time: 399ms
memory: 190912kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 3808kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 3640kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 3688kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 3692kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 3668kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 3728kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 3824kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 3852kb
Test #9:
score: 5
Accepted
time: 23ms
memory: 3944kb
Test #10:
score: 5
Accepted
time: 18ms
memory: 3812kb
Test #11:
score: 5
Accepted
time: 191ms
memory: 181652kb
Test #12:
score: 5
Accepted
time: 215ms
memory: 181352kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 5468kb
Test #14:
score: 5
Accepted
time: 3ms
memory: 5488kb
Test #15:
score: 5
Accepted
time: 116ms
memory: 5396kb
Test #16:
score: 5
Accepted
time: 121ms
memory: 5328kb
Test #17:
score: 5
Accepted
time: 14ms
memory: 20636kb
Test #18:
score: 5
Accepted
time: 19ms
memory: 21660kb
Test #19:
score: 5
Accepted
time: 374ms
memory: 181476kb
Test #20:
score: 5
Accepted
time: 401ms
memory: 190972kb
Extra Test:
score: 0
Extra Test Passed