#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 123456789
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 200050;
const int maxm = 800050;
int n, m, q;
vi ed[maxn];
vi ord;
int mn[maxm];
int mx[maxm];
int logs[maxn];
int pos[maxn];
void dfs(int u, int p) {
pos[u] = ord.size();
ord.pb(u);
for (int v : ed[u]) {
if (v != p) {
dfs(v, u);
}
}
}
void bld(int node, int ss, int se) {
if (ss == se) {
mn[node] = ord[ss];
mx[node] = ord[ss];
return;
}
int mid = ss + se >> 1;
bld(node * 2, ss, mid);
bld(node * 2 + 1, mid + 1, se);
mn[node] = min(mn[node * 2], mn[node * 2 + 1]);
mx[node] = max(mx[node * 2], mx[node * 2 + 1]);
}
int getmn(int node, int ss, int se, int l, int r) {
if (ss > se || ss > r || se < l) return 1e9;
if (l <= ss && se <= r) return mn[node];
int mid = ss + se >> 1;
return min(getmn(node * 2, ss, mid, l, r), getmn(node * 2 + 1, mid + 1, se, l, r));
}
int getmx(int node, int ss, int se, int l, int r) {
if (ss > se || ss > r || se < l) return 0;
if (l <= ss && se <= r) return mx[node];
int mid = ss + se >> 1;
return max(getmx(node * 2, ss, mid, l, r), getmx(node * 2 + 1, mid + 1, se, l, r));
}
int inter(pi X, pi Y) {
if (X.se < Y.fi) return 0;
if (X.fi > Y.se) return 0;
return 1;
}
vi check_validity(int N, vi u, vi v, vi s, vi e, vi l, vi r) {
n = N, m = u.size(), q = (int) s.size();
for (int i = 0; i < m; i++) {
ed[u[i]].pb(v[i]);
ed[v[i]].pb(u[i]);
}
int st = 0;
for (int i = 0; i < n; i++)
if (ed[i].size() <= 1) st = i;
dfs(st, st);
assert((int) ord.size() == n);
bld(1, 0, n - 1);
vi res(n);
for (int i = 0; i < q; i++) {
s[i] = pos[s[i]]; e[i] = pos[e[i]];
pi x = {s[i], s[i]}, y = {e[i], e[i]};
{
int bot = 0, top = s[i] - 1;
while (bot <= top) {
int mid = bot + top >> 1;
if (getmn(1, 0, n - 1, mid, s[i] - 1) >= l[i]) {
x.fi = mid;
top = mid - 1;
} else bot = mid + 1;
}
}
{
int bot = s[i] + 1, top = n - 1;
while (bot <= top) {
int mid = bot + top >> 1;
if (getmn(1, 0, n - 1, s[i] + 1, mid) >= l[i]) {
x.se = mid;
bot = mid + 1;
} else top = mid - 1;
}
}
{
int bot = 0, top = e[i] - 1;
while (bot <= top) {
int mid = bot + top >> 1;
if (getmx(1, 0, n - 1, mid, e[i] - 1) <= r[i]) {
y.fi = mid;
top = mid - 1;
} else bot = mid + 1;
}
}
{
int bot = e[i] + 1, top = n - 1;
while (bot <= top) {
int mid = bot + top >> 1;
if (getmx(1, 0, n - 1, e[i] + 1, mid) <= r[i]) {
y.se = mid;
bot = mid + 1;
} else top = mid - 1;
}
}
cout << x.fi << " " << x.se << " " << y.fi << " " << y.se << "\n";
res[i] = inter(x, y);
}
return res;
}
Compilation message
werewolf.cpp: In function 'void bld(int, int, int)':
werewolf.cpp:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = ss + se >> 1;
| ^
werewolf.cpp: In function 'int getmn(int, int, int, int, int)':
werewolf.cpp:47:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int mid = ss + se >> 1;
| ^
werewolf.cpp: In function 'int getmx(int, int, int, int, int)':
werewolf.cpp:53:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = ss + se >> 1;
| ^
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:80:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int mid = bot + top >> 1;
| ~~~~^~~~~
werewolf.cpp:90:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
90 | int mid = bot + top >> 1;
| ~~~~^~~~~
werewolf.cpp:100:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
100 | int mid = bot + top >> 1;
| ~~~~^~~~~
werewolf.cpp:110:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
110 | int mid = bot + top >> 1;
| ~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
341 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
341 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4049 ms |
41052 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
341 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
