#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int inf = 2e9;
struct ST_min {
int t[4 * N];
void build(int v, int tl, int tr, vector<int>&x) {
if (tl + 1 == tr) {
if (tl < x.size())
t[v] = x[tl];
else
t[v] = inf;
return;
}
int m = (tl + tr) / 2;
build(2 * v + 1, tl, m, x);
build(2 * v + 2, m, tr, x);
t[v] = min(t[2 * v + 1], t[2 * v + 2]);
}
int get(int v, int tl, int tr, int l, int r) {
if (tl >= r || tr <= l)
return inf;
if (tl >= l && tr <= r)
return t[v];
int m = (tl + tr) / 2;
int p1 = get(2 * v + 1, tl, m, l, r);
int p2 = get(2 * v + 2, m, tr, l, r);
return min(p1, p2);
}
};
struct ST_max {
int t[4 * N];
void build(int v, int tl, int tr, vector<int>&x) {
if (tl + 1 == tr) {
if (tl < x.size())
t[v] = x[tl];
else
t[v] = -inf;
return;
}
int m = (tl + tr) / 2;
build(2 * v + 1, tl, m, x);
build(2 * v + 2, m, tr, x);
t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
int get(int v, int tl, int tr, int l, int r) {
if (tl >= r || tr <= l)
return -inf;
if (tl >= l && tr <= r)
return t[v];
int m = (tl + tr) / 2;
int p1 = get(2 * v + 1, tl, m, l, r);
int p2 = get(2 * v + 2, m, tr, l, r);
return max(p1, p2);
}
};
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) {
int m = X.size(), q = S.size();
vector<vector<int>> g(n);
for (int i = 0; i < m; i++)
g[X[i]].push_back(Y[i]), g[Y[i]].push_back(X[i]);
vector<int> a(n);
int s;
for (int i = 0; i < n; i++)
if (g[i].size() == 1) {
s = i;
a[0] = i, a[1] = g[i].front();
break;
}
for (int i = 2; i < n; i++) {
int x = g[a[i - 1]].front(), y = g[a[i - 1]].back();
if (x != a[i - 2])
a[i] = x;
else
a[i] = y;
}
vector<int> p(n);
for (int i = 0; i < n; i++)
p[a[i]] = i;
ST_min mn; ST_max mx;
mn.build(0, 0, n, a);
mx.build(0, 0, n, a);
vector<int> ans(q, 0);
for (int i = 0; i < q; i++) {
int s = p[S[i]], e = p[E[i]];
if (s < e) {
int l = s, r = n;
while (r - l > 1) {
int c = (r + l) / 2;
if (mn.get(0, 0, n, s, c+1) >= L[i])
l = c;
else
r = c;
}
if (r >= e) {
ans[i] = 1;
continue;
}
ans[i] = mx.get(0, 0, n, l, E[i]+1) <= R[i];
} else {
int l = e, r = n;
while (r - l > 1) {
int c = (r + l) / 2;
if (mx.get(0, 0, n, s, c+1) <= R[i])
l = c;
else
r = c;
}
if (r >= s) {
ans[i] = 1;
continue;
}
ans[i] = mn.get(0, 0, n, l, e+1) >= L[i];
}
}
return ans;
}
Compilation message
werewolf.cpp: In member function 'void ST_min::build(int, int, int, std::vector<int>&)':
werewolf.cpp:12:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | if (tl < x.size())
| ~~~^~~~~~~~~~
werewolf.cpp: In member function 'void ST_max::build(int, int, int, std::vector<int>&)':
werewolf.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if (tl < x.size())
| ~~~^~~~~~~~~~
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:70:9: warning: variable 's' set but not used [-Wunused-but-set-variable]
70 | int s;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
834 ms |
29292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
