| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1256262 | nibert | Obstacles for a Llama (IOI25_obstacles) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
struct RollbackDSU {
vector<int> p, sz;
vector<pair<int,int>> stk;
RollbackDSU(int n) : p(n), sz(n,1) { iota(p.begin(), p.end(), 0); }
int find(int x) { while (x != p[x]) x = p[x]; return x; }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a,b);
stk.push_back({b, sz[a]});
p[b] = a; sz[a] += sz[b];
return true;
}
int snapshot() { return (int)stk.size(); }
void rollback(int t) {
while ((int)stk.size() > t) {
auto [b, sa] = stk.back(); stk.pop_back();
int a = p[b];
p[b] = b; sz[a] = sa;
}
}
};
inline int cell_id(int i, int j, int M) { return i*M + j; }
struct Query {
int L, R, S, D, idx;
};
int N, M, Q;
vector<int> T, H;
vector<vector<int>> free_rows; // free_rows[j] = rows free in column j
void initialize(vector<int> t, vector<int> h) {
T = t; H = h;
N = T.size(); M = H.size();
free_rows.assign(M, {});
for (int j = 0; j < M; j++) {
for (int i = 0; i < N; i++) {
if (T[i] > H[j]) free_rows[j].push_back(i);
}
}
}
vector<int> process_queries(vector<Query> &queries) {
int B = max(1, (int)(sqrt(M)));
sort(queries.begin(), queries.end(), [&](const Query &a, const Query &b) {
int blA = a.L / B, blB = b.L / B;
if (blA != blB) return blA < blB;
return a.R < b.R;
});
RollbackDSU dsu(N*M);
vector<int> ans(Q, 0);
vector<int> col_snapshot(M, -1);
vector<bool> active(M, false);
int curL = 0, curR = -1;
auto add_col = [&](int c) {
int snap = dsu.snapshot();
// Vertical edges
auto &rows = free_rows[c];
for (int k = 0; k+1 < (int)rows.size(); k++) {
if (rows[k+1] == rows[k]+1) {
dsu.unite(cell_id(rows[k], c, M), cell_id(rows[k+1], c, M));
}
}
// Horizontal edges
if (c > 0 && active[c-1]) {
auto &left = free_rows[c-1];
auto &cur = free_rows[c];
// intersect sorted lists
int p1=0, p2=0;
while (p1<(int)left.size() && p2<(int)cur.size()) {
if (left[p1] == cur[p2]) {
dsu.unite(cell_id(left[p1], c-1, M), cell_id(cur[p2], c, M));
p1++; p2++;
} else if (left[p1] < cur[p2]) p1++;
else p2++;
}
}
if (c+1 < M && active[c+1]) {
auto &right = free_rows[c+1];
auto &cur = free_rows[c];
int p1=0, p2=0;
while (p1<(int)right.size() && p2<(int)cur.size()) {
if (right[p1] == cur[p2]) {
dsu.unite(cell_id(right[p1], c+1, M), cell_id(cur[p2], c, M));
p1++; p2++;
} else if (right[p1] < cur[p2]) p1++;
else p2++;
}
}
active[c] = true;
col_snapshot[c] = snap;
};
auto remove_col = [&](int c) {
dsu.rollback(col_snapshot[c]);
active[c] = false;
};
for (auto &qu : queries) {
while (curR < qu.R) add_col(++curR);
while (curR > qu.R) remove_col(curR--);
while (curL < qu.L) remove_col(curL++);
while (curL > qu.L) add_col(--curL);
int idS = cell_id(0, qu.S, M);
int idD = cell_id(0, qu.D, M);
ans[qu.idx] = (dsu.find(idS) == dsu.find(idD));
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
T.resize(N); H.resize(M);
for(int i=0;i<N;i++) cin >> T[i];
for(int j=0;j<M;j++) cin >> H[j];
initialize(T, H);
cin >> Q;
vector<Query> queries(Q);
for(int i=0;i<Q;i++){
cin >> queries[i].L >> queries[i].R >> queries[i].S >> queries[i].D;
queries[i].idx = i;
}
vector<int> ans = process_queries(queries);
for(int x: ans) cout << x << "\n";
}