#include "werewolf.h"
#include <bits/stdc++.h>
struct UnionFind {
int n;
std::vector<int> data;
UnionFind(int n_) : n(n_) {
data.assign(n, -1);
}
int find(int v) {
if (data[v] < 0) return v;
else return data[v] = find(data[v]);
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (data[a] > data[b]) std::swap(a, b);
data[a] += data[b];
data[b] = a;
}
};
constexpr int inf = 1 << 30;
template <class M>
class SegmentTree {
using T = typename M::T;
int n, size;
std::vector<T> data;
void update(int i) {
data[i] = M::op(data[2 * i], data[2 * i + 1]);
}
public:
SegmentTree() {}
SegmentTree(const std::vector<T> &vec) {
n = (int)vec.size();
size = 1;
while (size < n) {
size *= 2;
}
data.assign(2 * size, M::e());
std::copy(vec.begin(), vec.end(), data.begin() + size);
for (int i = size - 1; i >= 1; --i) update(i);
}
void set(int i, const T &v) {
i += size;
data[i] = v;
while (i != 1) {
i /= 2;
update(i);
}
}
T fold(int l, int r) {
T pl = M::e(), pr = M::e();
for (l += size, r += size; l < r; l /= 2, r /= 2) {
if (l & 1) pl = M::op(pl, data[l++]);
if (r & 1) pr = M::op(data[--r], pr);
}
return M::op(pl, pr);
}
int max_right(int l, int v) {
int ok = n, ng = l;
while (ok - ng > 1) {
const auto mid = (ok + ng) / 2;
if (fold(l, mid).second <= v) ng = mid;
else ok = mid;
}
return ng;
}
int min_left(int r, int v) {
int ok = -1, ng = r;
while (ng - ok > 1) {
const auto mid = (ok + ng) / 2;
if (fold(mid, r).second <= v) ng = mid;
else ok = mid;
}
return ng;
}
};
struct MonoidMinMax {
using T = std::pair<int, int>;
static T op(const T &a, const T &b) {
return {std::min(a.first, b.first), std::max(a.second, b.second)};
}
static T e() {
return {inf, -1};
}
};
constexpr int B = 3;
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S,
std::vector<int> E, std::vector<int> L, std::vector<int> R) {
const int M = (int)X.size();
const int Q = (int)S.size();
std::vector<int> answer(Q);
std::vector<std::vector<int>> graph(N);
for (int i = 0; i < M; ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
int v = -1;
for (int i = 0; i < N; ++i) {
if (graph[i].size() == 1) {
v = i;
}
}
std::vector<int> id(N), rid(N);
{
int p = -1;
int cnt = 0;
while (true) {
id[v] = cnt;
rid[cnt] = v;
++cnt;
int w = v;
for (const int t : graph[v]) if (t != p) {
p = v;
v = t;
break;
}
if (w == v) {
break;
}
}
}
std::vector<std::pair<int, int>> vec(N);
for (int i = 0; i < N; ++i) {
vec[i] = {rid[i], rid[i]};
}
SegmentTree<MonoidMinMax> seg(vec);
for (int i = 0; i < Q; ++i) {
const int a = id[S[i]], b = id[E[i]];
if (a < b) {
const int x = seg.min_left(b + 1, R[i]);
if (x <= a) {
answer[i] = true;
} else {
if (seg.fold(a, x).first >= L[i]) answer[i] = true;
else answer[i] = false;
}
} else {
const int x = seg.max_right(b, R[i]);
if (x >= a) {
answer[i] = true;
} else {
if (seg.fold(x, a + 1).first >= L[i]) answer[i] = true;
else answer[i] = false;
}
}
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
550 ms |
28700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
