#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int maxn = 200001;
int ind[maxn], tree[4 * maxn][2][2];
vector <int> b[maxn], v[maxn], ret;
void update(int l, int r, int node, int ind, int val, int idx){
if(r < l) return;
if(r < ind || l > ind) return;
if(l == r){
tree[node][0][idx] = tree[node][1][idx] = val;
return;
}
int mid = (l + r) / 2;
update(l, mid, 2 * node, ind, val, idx);
update(mid + 1, r, 2 * node + 1, ind, val, idx);
tree[node][0][idx] = min(tree[2 * node][0][idx], tree[2 * node + 1][0][idx]);
tree[node][1][idx] = max(tree[2 * node][1][idx], tree[2 * node + 1][1][idx]);
}
int query(int l, int r, int node, int s, int e, int mx, int idx){
if(r < l) return (mx == 0 ? 1e9 : -1);
if(r < s || l > e) return (mx == 0 ? 1e9 : -1);
if(s <= l && r <= e) return tree[node][mx][idx];
int mid = (l + r) / 2;
if(mx) return max(query(l, mid, 2 * node, s, e, mx, idx), query(mid + 1, r, 2 * node + 1, s, e, mx, idx));
return min(query(l, mid, 2 * node, s, e, mx, idx), query(mid + 1, r, 2 * node + 1, s, e, mx, idx));
}
vector <int> check_validity(int N, vector <int> X, vector <int> Y,
vector <int> S, vector <int> E,
vector <int> L, vector <int> R) {
for(int i = 0 ; i < X.size() ; i++){
v[X[i]].push_back(Y[i]);
v[Y[i]].push_back(X[i]);
}
int start[2] = {-1, -1};
for(int i = 0 ; i < N ; i++)
if(v[i].size() == 1){
if(start[0] == -1) start[0] = i;
else start[1] = i;
}
if(start[0] == -1 || start[1] == -1) while(1);
/*
b[0].push_back(start[0]);
b[0].push_back(v[start[0]][0]);
while(b[0].size() != N){
int f = v[b[0].back()][0], s = v[b[0].back()][1];
b[0].push_back(f + s - b[0][b[0].size() - 2]);
}
b[1].push_back(start[1]);
b[1].push_back(v[start[1]][0]);
for(int i = 1 ; i <= N - 2 ; i++){
// int f = v[b[1].back()][0], s = v[b[1].back()][1];
int f = 1, s = 2;
//b[1].push_back(f + s - b[1][b[1].size() - 2]);
b[1].push_back(1);
}*/
/*
for(int i = 0 ; i < N ; i++)
b[0].push_back(i);
for(int i = 0 ; i < N ; i++)
b[1].push_back(i);
*/
for(int i = 0 ; i < N ; i++){
// update(0, N - 1, 1, i, b[0][i], 0);
// update(0, N - 1, 1, i, b[1][i], 1);
}
for(int i = 0 ; i < b[0].size() ; i++)
ind[b[0][i]] = i;
for(int i = 0 ; i < S.size() ; i++){
int s = S[i], e = E[i];
if(s == e){
if(s >= L[i] && s <= R[i]) ret.push_back(1);
else ret.push_back(0);
continue;
}
s = ind[s];
e = ind[e];
vector <int> &a = b[0];
int idx = 0;
if(e < s){
a = b[1];
idx = 1;
s = N - s - 1;
e = N - e - 1;
}
int l = s, r = e;
/*
while(l <= r){
int mid = (l + r) / 2;
if(query(0, N - 1, 1, l, mid, 0, idx) >= L[i]) l = mid + 1;
else r = mid - 1;
}
*/
int y = r + 1;
l = s, r = e;
/*
while(l <= r){
int mid = (l + r) / 2;
if(query(0, N - 1, 1, mid, r, 1, idx) <= R[i]) r = mid - 1;
else l = mid + 1;
}
*/
int x = l - 1;
x++;
y--;
if(x <= y) ret.push_back(1);
else ret.push_back(0);
}
return ret;
}
Compilation message
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:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < X.size() ; i++){
~~^~~~~~~~~~
werewolf.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < b[0].size() ; i++)
~~^~~~~~~~~~~~~
werewolf.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < S.size() ; i++){
~~^~~~~~~~~~
werewolf.cpp:87:13: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
int idx = 0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
297 ms |
27172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
9724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
