#include "werewolf.h"
#include<bits/stdc++.h>
#define N 200010
#define inf 1e8
using namespace std;
int v[N];
struct SegtreeMin{
int tree[4*N];
int join(int a, int b){
return min(a, b);
}
void build(int node, int l, int r){
if(l == r){
tree[node] = v[l];
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
int query(int node, int l, int r, int tl, int tr){
if(l > tr or tl > r) return inf;
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
int search(int n, int l, int r, int val, int typ){
if(query(1, l, r, 1, n) >= val) return 0;
if(typ == 0){
while(r-l > 1){
int mid = (l+r)/2;
// cout << l << ' ' << r << ' ' << mid << endl;
int q = query(1, l, mid, 1, n);
if(q < val) r = mid;
else l = mid+1;
}
if(query(1, l, l, 1, n) < val) return l;
else return r;
}
else {
while(l < r){
int mid = (l+r)/2;
int q = query(1,mid+1, r, 1, n);
if(q < val) l = mid+1;
else r = mid;
}
return l;
}
}
} segmin;
struct SegtreeMax{
int tree[4*N];
int join(int a, int b){
return max(a, b);
}
void build(int node, int l, int r){
if(l == r){
tree[node] = v[l];
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = join(tree[2*node], tree[2*node+1]);
return;
}
int query(int node, int l, int r, int tl, int tr){
if(l > tr or tl > r) return -1;
if(l <= tl and tr <= r) return tree[node];
int mid = (tl+tr)/2;
return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
}
} segmax;
vector <int> g[N];
int inv[N];
void construct(int n){
int st = 0, ed = 0;
for(int i = 1;i <= n;i++){
if(g[i].size() == 1){
ed = st;
st = i;
}
}
// cout << st << ' ';
v[1] = st;
inv[st] = 1;
st = g[st][0];
for(int i = 2;i <= n;i++){
v[i] = st;
inv[st] = i;
if(i < n){
int x = g[st][0];
if(inv[x] != 0) x = g[st][1];
st = x;
}
}
return;
}
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) {
for(int i = 0;i < n-1;i++){
int a = ++x[i], b = ++y[i];
g[a].push_back(b);
g[b].push_back(a);
}
construct(n);
segmin.build(1, 1, n);
segmax.build(1, 1, n);
vector <int> res;
// for(int i = 1;i <= n;i++){
// cout << v[i] << ' ' << inv[v[i]] << endl;
// }
for(int i = 0;i < s.size();i++){
int st = ++s[i], ed = ++e[i], lt = ++l[i], rt = ++r[i];
st = inv[st];
ed = inv[ed];
if(v[st] < lt){
res.push_back(0);
continue;
}
if(v[ed] > rt){
res.push_back(0);
continue;
}
if(st <= ed){
int w = segmin.search(n, st, ed, lt, 0);
if(w == 0){
res.push_back(1);
continue;
}
int h = segmax.query(1, w, ed, 1, n);
if(h > rt){
res.push_back(0);
continue;
}
res.push_back(1);
continue;
}
else{
int w = segmin.search(n, ed, st, lt, 1);
if(w == 0){
res.push_back(1);
continue;
}
int h = segmax.query(1, ed, w, 1, n);
if(h > rt){
res.push_back(0);
continue;
}
res.push_back(1);
continue;
}
}
return res;
// int Q = S.size();
// std::vector<int> A(Q);
// for (int i = 0; i < Q; ++i) {
// A[i] = 0;
// }
// return A;
}
Compilation message
werewolf.cpp: In function 'void construct(int)':
werewolf.cpp:86:15: warning: variable 'ed' set but not used [-Wunused-but-set-variable]
86 | int st = 0, ed = 0;
| ^~
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:124:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int i = 0;i < s.size();i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
16988 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
16988 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
801 ms |
38088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
16988 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
