#include <bits/stdc++.h>
#include "werewolf.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
struct Seg {
int n;
vii seg;
Seg (int m) {
for (n = 1; n < m; n <<= 1);
seg.resize(2 * n, {0, n});
}
void update(int i, int x) {
for (i += n; i; i >>= 1) {
chkmax(seg[i].x, x);
chkmin(seg[i].y, x);
}
}
pii query(int l, int r) {
pii ans = {0, n};
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
chkmax(ans.x, seg[l].x);
chkmin(ans.y, seg[l].y);
l++;
}
if (r & 1) {
--r;
chkmax(ans.x, seg[r].x);
chkmin(ans.y, seg[r].y);
}
}
return ans;
}
};
void DfsMax(vvi &graph, int node, int max, vb &visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (neighbor <= max && !visited[neighbor]) DfsMax(graph, neighbor, max, visited);
}
}
void DfsMin(vvi &graph, int node, int min, vb &visited) {
visited[node] = true;
for (int neighbor : graph[node]) {
if (neighbor >= min && !visited[neighbor]) DfsMin(graph, neighbor, min, visited);
}
}
const int MAX_N = 2e5 + 5;
int ind[MAX_N];
vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {
int m = x.size();
vvi graph(n);
for (int i = 0; i < m; i++) {
graph[x[i]].push_back(y[i]);
graph[y[i]].push_back(x[i]);
}
int start = 0;
for (; start < n; start++) {
if (graph[start].size() == 1) break;
}
bitset<MAX_N> visited;
for (int i = 0; i < n; i++) {
ind[start] = i;
visited[start] = true;
for (int neighbor : graph[start]) {
if (!visited[neighbor]) {
start = neighbor;
break;
}
}
}
Seg seg(n);
for (int i = 0; i < n; i++) {
seg.update(ind[i], i);
}
int q = s.size();
vi ans(q);
for (int i = 0; i < q; i++) {
if (s[i] < l[i] || r[i] < e[i]) continue;
int v = ind[s[i]], u = ind[e[i]];
if (v < u) {
int begin = v, end = u + 1, mid;
while (begin < end) {
mid = (begin + end) >> 1;
if (seg.query(v, mid + 1).y < l[i]) end = mid;
else begin = mid + 1;
}
int right = end - 1;
begin = v, end = u;
while (begin < end) {
mid = (begin + end) >> 1;
if (seg.query(mid, u).x > r[i]) begin = mid + 1;
else end = mid;
}
int left = end;
ans[i] = right >= left;
} else {
int begin = v, end = u + 1, mid;
while (begin < end) {
mid = (begin + end) >> 1;
if (seg.query(v, mid + 1).x > r[i]) end = mid;
else begin = mid + 1;
}
int right = end - 1;
begin = v, end = u;
while (begin < end) {
mid = (begin + end) >> 1;
if (seg.query(mid, u).y < l[i]) begin = mid + 1;
else end = mid;
}
int left = end;
ans[i] = right >= left;
}
// vb visited1(n), visited2(n);
// DfsMin(graph, s[i], l[i], visited1);
// DfsMax(graph, e[i], r[i], visited2);
// for (int j = 0; j < n; j++) {
// if (visited1[j] && visited2[j]) {
// ans[i] = 1;
// break;
// }
// }
}
return ans;
}
//6 6 3
//0 3
//1 2
//1 5
//1 3
//2 5
//3 4
//
//4 2 1 2
//4 2 2 2
//5 4 3 4
//6 5 3
//1 3
//3 0
//0 4
//4 5
//5 2
//
//3 5 0 5
//2 1 0 4
//4 2 3 4
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
519 ms |
26376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
