#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "werewolf.h"
template<typename T>
struct sparse_table1 {
/*============================*/
T merge(T a, T b) {
return min(a,b);
}
/*============================*/
vector<vector<T>> table;
vector<int> bin_log;
int LOG = 0;
sparse_table1() {
}
sparse_table1(vector<T> &a, int n) {
while ((1 << LOG) <= n) LOG++;
table = vector<vector<T>>(n, vector<T>(LOG));
bin_log = vector<int>(n + 1);
rep(i, n) table[i][0] = a[i];
rep1(j, LOG - 1) {
rep(i, n) {
int jump = 1 << (j - 1);
if (i + jump >= n) {
break;
}
table[i][j] = merge(table[i][j - 1], table[i + jump][j - 1]);
}
}
bin_log[1] = 0;
for (int i = 2; i <= n; ++i) {
bin_log[i] = bin_log[i / 2] + 1;
}
}
T query(int l, int r) {
int len = r - l + 1;
int k = bin_log[len];
T val1 = table[l][k];
T val2 = table[r - (1 << k) + 1][k];
return merge(val1, val2);
}
};
template<typename T>
struct sparse_table2 {
/*============================*/
T merge(T a, T b) {
return max(a,b);
}
/*============================*/
vector<vector<T>> table;
vector<int> bin_log;
int LOG = 0;
sparse_table2() {
}
sparse_table2(vector<T> &a, int n) {
while ((1 << LOG) <= n) LOG++;
table = vector<vector<T>>(n, vector<T>(LOG));
bin_log = vector<int>(n + 1);
rep(i, n) table[i][0] = a[i];
rep1(j, LOG - 1) {
rep(i, n) {
int jump = 1 << (j - 1);
if (i + jump >= n) {
break;
}
table[i][j] = merge(table[i][j - 1], table[i + jump][j - 1]);
}
}
bin_log[1] = 0;
for (int i = 2; i <= n; ++i) {
bin_log[i] = bin_log[i / 2] + 1;
}
}
T query(int l, int r) {
int len = r - l + 1;
int k = bin_log[len];
T val1 = table[l][k];
T val2 = table[r - (1 << k) + 1][k];
return merge(val1, val2);
}
};
vector<int> adj[N];
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> T,
std::vector<int> L, std::vector<int> R) {
int m = sz(X), q = sz(S);
rep(i,m){
int u = X[i], v = Y[i];
adj[u].pb(v), adj[v].pb(u);
}
int root = -1;
rep(i,n){
if(sz(adj[i]) == 1){
root = i;
}
}
assert(root != -1);
vector<int> order;
int curr = root, par = -1;
while(true){
order.pb(curr);
int nxt = -1;
trav(v,adj[curr]){
if(v != par){
nxt = v;
}
}
if(nxt == -1) break;
par = curr;
curr = nxt;
}
vector<int> pos(n);
rep(i,n) pos[order[i]] = i;
sparse_table1<int> st_min(order,n);
sparse_table2<int> st_max(order,n);
vector<int> ans(q);
rep(i,q){
int s = S[i], t = T[i], lx = L[i], rx = R[i];
int ls = -1, rs = -1, lt = -1, rt = -1;
{
int lo = 0, hi = pos[s];
while(lo <= hi){
int mid = (lo+hi) >> 1;
if(st_min.query(mid,pos[s]) >= lx){
ls = mid;
hi = mid-1;
}
else{
lo = mid+1;
}
}
}
{
int lo = pos[s], hi = n-1;
while(lo <= hi){
int mid = (lo+hi) >> 1;
if(st_min.query(pos[s],mid) >= lx){
rs = mid;
lo = mid+1;
}
else{
hi = mid-1;
}
}
}
{
int lo = 0, hi = pos[t];
while(lo <= hi){
int mid = (lo+hi) >> 1;
if(st_max.query(mid,pos[t]) <= rx){
lt = mid;
hi = mid-1;
}
else{
lo = mid+1;
}
}
}
{
int lo = pos[t], hi = n-1;
while(lo <= hi){
int mid = (lo+hi) >> 1;
if(st_max.query(pos[t],mid) <= rx){
rt = mid;
lo = mid+1;
}
else{
hi = mid-1;
}
}
}
// do [ls,rs] and [lt,rt] have at least 1 point in common?
if(min(rs,rt) >= max(ls,lt)){
ans[i] = 1;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
793 ms |
73840 KB |
Output is correct |
| 2 |
Correct |
1012 ms |
72100 KB |
Output is correct |
| 3 |
Correct |
985 ms |
72096 KB |
Output is correct |
| 4 |
Correct |
1020 ms |
72108 KB |
Output is correct |
| 5 |
Correct |
1026 ms |
72092 KB |
Output is correct |
| 6 |
Correct |
902 ms |
72108 KB |
Output is correct |
| 7 |
Correct |
927 ms |
72096 KB |
Output is correct |
| 8 |
Correct |
813 ms |
71884 KB |
Output is correct |
| 9 |
Correct |
429 ms |
71868 KB |
Output is correct |
| 10 |
Correct |
352 ms |
72112 KB |
Output is correct |
| 11 |
Correct |
371 ms |
71876 KB |
Output is correct |
| 12 |
Correct |
416 ms |
72008 KB |
Output is correct |
| 13 |
Correct |
1073 ms |
72132 KB |
Output is correct |
| 14 |
Correct |
1041 ms |
71880 KB |
Output is correct |
| 15 |
Correct |
1066 ms |
72104 KB |
Output is correct |
| 16 |
Correct |
1140 ms |
72096 KB |
Output is correct |
| 17 |
Correct |
986 ms |
73036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
