#include <bits/stdc++.h>
//#include "werewolf.h"
#define Read_Input true
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long
template <class _T>
bool chmin(_T &x, const _T &y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag = false;
if ( x < y ){
x = y; flag |= true;
}
return flag;
}
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 = (int)X.size(), q = (int)S.size();
vector <int> g[n];
for ( int i = 0; i < m; i++ ){
g[X[i]].pb(Y[i]);
g[Y[i]].pb(X[i]);
}
int root = -1;
for ( int i = 0; i < n; i++ ){
if ( (int)g[i].size() == 1 ){
root = i;
}
}
vector <int> ord, pos(n, -1);
ord.pb(root);
while ( (int)ord.size() < n ){
int sz = (int)ord.size();
for ( auto to: g[ord.back()] ){
if ( sz == 1 or to != ord[sz - 2] ){
ord.pb(to); break;
}
}
}
const int inf = 1e9 + 1;
struct Sp{
vector <vector<int>> T;
Sp(vector <int> def){
int n = (int)def.size();
T.resize(21); T[0].resize(n);
for ( int i = 0; i < n; i++ ){
T[0][i] = def[i];
}
for ( int i = 1; i < 21; i++ ){
int k = 1 << i - 1;
T[i].resize(n);
for ( int j = 0; j < n; j++ ){
T[i][j] = min(T[i - 1][j], T[i - 1][min(j + k, n - 1)]);
}
}
}
int get(int l, int r){
if ( l > r ) swap(l, r);
int lg = __lg(r - l + 1), k = 1 << lg;
return min(T[lg][l], T[lg][r - k + 1]);
}
};
for ( int i = 0; i < n; i++ ){
pos[ord[i]] = i;
}
Sp Mn(ord);
for ( auto &i: ord ) i *= -1;
Sp Mx(ord);
auto query = [&](int l, int r, int L, int R){
l = pos[l], r = pos[r];
if ( -ord[l] < L or -ord[r] > R ){
return false;
}
int tl = l, tr = r + (l < r ? 1 : -1), x = -1, y = n;
while ( abs(tl - tr) > 1 ){
int md = (tl + tr) >> 1;
if ( Mn.get(tl, md) < L ){
tr = md;
}
else tl = md + 1;
} x = tl;
tl = l - (l < r ? 1 : -1), tr = r;
while ( abs(tl - tr) > 1 ){
int md = (tl + tr) >> 1;
if ( -Mx.get(md, tr) > R ){
tl = md;
} else tr = md;
} y = tr;
return l < r ? x >= y : x <= y;
};
vector <int> ans(q);
for ( int i = 0; i < q; i++ ){
ans[i] = query(S[i], E[i], L[i], R[i]);
}
return ans;
}
#ifndef EVAL
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q; cin >> n >> m >> q;
vector <int> x(m), y(m);
for ( auto &i: x ) cin >> i;
for ( auto &i: y ) cin >> i;
vector <int> s(q), e(q), l(q), r(q);
for ( auto &i: s ) cin >> i;
for ( auto &i: e ) cin >> i;
for ( auto &i: l ) cin >> i;
for ( auto &i: r ) cin >> i;
for ( auto i: check_validity(n, x, y, s, e, l, r) ){
cout << i << ' ';
}
cout << '\n';
}
/*
6 6 3
5 1 1 3 3 5
1 2 3 4 0 2
4 4 5
2 2 4
1 2 3
2 2 4
answer : {1, 0 ,0}
*/
#endif // EVAL
Compilation message
werewolf.cpp: In constructor 'check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::Sp::Sp(std::vector<int>)':
werewolf.cpp:65:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
65 | int k = 1 << i - 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:55:15: warning: unused variable 'inf' [-Wunused-variable]
55 | const int inf = 1e9 + 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4014 ms |
260 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4014 ms |
260 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4041 ms |
56964 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4014 ms |
260 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
