#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
template<typename T> class fenwick_t {
public:
vector<T> fenw;
int n;
fenwick_t(int n):n(n) {
fenw.resize(n);
}
void modify(int x, T value) {
while (x < n) {
fenw[x] += value;
x |= x + 1;
}
}
T query(int x) {
T result{};
while (x >= 0) {
result += fenw[x];
x = (x & x + 1) - 1;
}
return result;
}
};
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
int m = x.size(), q = s.size();
struct tree_t {
struct edge_t {
int u, v, w;
edge_t(int u = 0, int v = 0, int w = 0):u(u), v(v), w(w) {
}
bool operator < (const edge_t &b) const {
return w < b.w;
}
};
vector<int> l, r, left, right, value;
vector<vector<int>> ancestor;
int n, log_n, total, counter;
vector<edge_t> edge;
tree_t(int n):n(n) {
l = r = left = right = value = vector<int> ((n << 1) - 1, -1);
total = n;
log_n = counter = 0;
while (1 << log_n <= n) {
++log_n;
}
ancestor = vector<vector<int>> (log_n, vector<int> ((n << 1) - 1, -1));
}
void dfs(int x) {
left[x] = counter++;
if (x >= n) {
dfs(l[x]);
dfs(r[x]);
}
right[x] = counter;
}
void init() {
sort(edge.begin(), edge.end());
vector<int> p((n << 1) - 1);
for (int i = 0; i < (n << 1) - 1; ++i) {
p[i] = i;
}
function<int(int)> find = [&](int x) {
while (x != p[x]) {
x = p[x] = p[p[x]];
}
return x;
};
total = n;
for (auto e : edge) {
if (find(e.u) != find(e.v)) {
l[total] = find(e.u);
r[total] = find(e.v);
ancestor[0][find(e.u)] = ancestor[0][find(e.v)] = total;
value[total] = e.w;
p[find(e.u)] = p[find(e.v)] = total;
total++;
}
}
for (int i = 1; i < log_n; ++i) {
for (int j = 0; j < (n << 1) - 1; ++j) {
if (~ancestor[i - 1][j]) {
ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
}
}
}
dfs(n - 1 << 1);
}
int go(int x, int limit) {
for (int i = log_n - 1; ~i; --i) {
if (~ancestor[i][x] && value[ancestor[i][x]] <= limit) {
x = ancestor[i][x];
}
}
return x;
}
};
tree_t prefix(n), suffix(n);
for (int i = 0; i < m; ++i) {
prefix.edge.emplace_back(x[i], y[i], max(x[i], y[i]));
suffix.edge.emplace_back(x[i], y[i], -min(x[i], y[i]));
}
prefix.init();
suffix.init();
vector<pair<int, int>> points;
fenwick_t<int> fenwick((n << 1) - 1);
for (int i = 0; i < n; ++i) {
points.emplace_back(prefix.left[i], suffix.left[i]);
}
sort(points.begin(), points.end());
struct event_t {
int x, l, r, id, sign;
event_t(int x = 0, int l = 0, int r = 0, int id = 0, int sign = 0):x(x), l(l), r(r), id(id), sign(sign) {
}
bool operator < (const event_t &b) const {
return x < b.x;
}
};
vector<event_t> events;
vector<int> answer(q);
for (int i = 0; i < q; ++i) {
int x = prefix.go(e[i], r[i]), y = suffix.go(s[i], -l[i]);
events.emplace_back(prefix.left[x], suffix.left[y], suffix.right[y], i, -1);
events.emplace_back(prefix.right[x], suffix.left[y], suffix.right[y], i, 1);
}
sort(events.begin(), events.end());
int current = 0;
for (auto event : events) {
while (current < n && points[current].first < event.x) {
fenwick.modify(points[current++].second, 1);
}
answer[event.id] += event.sign * (fenwick.query(event.r - 1) - fenwick.query(event.l - 1));
}
for (int i = 0; i < q; ++i) {
if (answer[i]) {
answer[i] = 1;
}
}
return answer;
}
Compilation message
werewolf.cpp: In member function 'void check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::tree_t::init()':
werewolf.cpp:102:13: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
dfs(n - 1 << 1);
~~^~~
werewolf.cpp: In instantiation of 'T fenwick_t<T>::query(int) [with T = int]':
werewolf.cpp:155:64: required from here
werewolf.cpp:26:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
x = (x & x + 1) - 1;
~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
368 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
356 KB |
Output is correct |
6 |
Correct |
2 ms |
356 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
368 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
356 KB |
Output is correct |
6 |
Correct |
2 ms |
356 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
11 ms |
1820 KB |
Output is correct |
11 |
Correct |
9 ms |
1792 KB |
Output is correct |
12 |
Correct |
8 ms |
1792 KB |
Output is correct |
13 |
Correct |
12 ms |
1784 KB |
Output is correct |
14 |
Correct |
12 ms |
1784 KB |
Output is correct |
15 |
Correct |
13 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1055 ms |
111788 KB |
Output is correct |
2 |
Correct |
1484 ms |
113260 KB |
Output is correct |
3 |
Correct |
1099 ms |
112256 KB |
Output is correct |
4 |
Correct |
1094 ms |
111760 KB |
Output is correct |
5 |
Correct |
916 ms |
111836 KB |
Output is correct |
6 |
Correct |
1066 ms |
111844 KB |
Output is correct |
7 |
Correct |
812 ms |
111768 KB |
Output is correct |
8 |
Correct |
1531 ms |
113276 KB |
Output is correct |
9 |
Correct |
788 ms |
112308 KB |
Output is correct |
10 |
Correct |
516 ms |
111848 KB |
Output is correct |
11 |
Correct |
535 ms |
111768 KB |
Output is correct |
12 |
Correct |
567 ms |
111700 KB |
Output is correct |
13 |
Correct |
1699 ms |
113488 KB |
Output is correct |
14 |
Correct |
1883 ms |
113336 KB |
Output is correct |
15 |
Correct |
1746 ms |
113396 KB |
Output is correct |
16 |
Correct |
1540 ms |
113360 KB |
Output is correct |
17 |
Correct |
776 ms |
111636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
368 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
356 KB |
Output is correct |
6 |
Correct |
2 ms |
356 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
3 ms |
384 KB |
Output is correct |
10 |
Correct |
11 ms |
1820 KB |
Output is correct |
11 |
Correct |
9 ms |
1792 KB |
Output is correct |
12 |
Correct |
8 ms |
1792 KB |
Output is correct |
13 |
Correct |
12 ms |
1784 KB |
Output is correct |
14 |
Correct |
12 ms |
1784 KB |
Output is correct |
15 |
Correct |
13 ms |
1920 KB |
Output is correct |
16 |
Correct |
1055 ms |
111788 KB |
Output is correct |
17 |
Correct |
1484 ms |
113260 KB |
Output is correct |
18 |
Correct |
1099 ms |
112256 KB |
Output is correct |
19 |
Correct |
1094 ms |
111760 KB |
Output is correct |
20 |
Correct |
916 ms |
111836 KB |
Output is correct |
21 |
Correct |
1066 ms |
111844 KB |
Output is correct |
22 |
Correct |
812 ms |
111768 KB |
Output is correct |
23 |
Correct |
1531 ms |
113276 KB |
Output is correct |
24 |
Correct |
788 ms |
112308 KB |
Output is correct |
25 |
Correct |
516 ms |
111848 KB |
Output is correct |
26 |
Correct |
535 ms |
111768 KB |
Output is correct |
27 |
Correct |
567 ms |
111700 KB |
Output is correct |
28 |
Correct |
1699 ms |
113488 KB |
Output is correct |
29 |
Correct |
1883 ms |
113336 KB |
Output is correct |
30 |
Correct |
1746 ms |
113396 KB |
Output is correct |
31 |
Correct |
1540 ms |
113360 KB |
Output is correct |
32 |
Correct |
776 ms |
111636 KB |
Output is correct |
33 |
Correct |
1496 ms |
112196 KB |
Output is correct |
34 |
Correct |
417 ms |
50684 KB |
Output is correct |
35 |
Correct |
1739 ms |
114236 KB |
Output is correct |
36 |
Correct |
1483 ms |
112164 KB |
Output is correct |
37 |
Correct |
1587 ms |
113568 KB |
Output is correct |
38 |
Correct |
1376 ms |
112720 KB |
Output is correct |
39 |
Correct |
1471 ms |
114804 KB |
Output is correct |
40 |
Correct |
1366 ms |
126676 KB |
Output is correct |
41 |
Correct |
999 ms |
112828 KB |
Output is correct |
42 |
Correct |
633 ms |
112176 KB |
Output is correct |
43 |
Correct |
1415 ms |
122156 KB |
Output is correct |
44 |
Correct |
1534 ms |
113412 KB |
Output is correct |
45 |
Correct |
985 ms |
115412 KB |
Output is correct |
46 |
Correct |
1034 ms |
115056 KB |
Output is correct |
47 |
Correct |
1647 ms |
113632 KB |
Output is correct |
48 |
Correct |
1785 ms |
113336 KB |
Output is correct |
49 |
Correct |
1571 ms |
113780 KB |
Output is correct |
50 |
Correct |
1422 ms |
113460 KB |
Output is correct |
51 |
Correct |
808 ms |
126920 KB |
Output is correct |
52 |
Correct |
867 ms |
126660 KB |
Output is correct |