#include <bits/stdc++.h>
//#include "werewolf.h"
using namespace std;
const int INF = 1e9;
struct SegTree {
struct Node {
int ma, mi;
Node(int m1, int m2) : ma(m1),mi(m2) {}
Node(int v) : ma(v), mi(v) {}
Node() : ma(-INF),mi(INF) {}
};
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=2;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
Node f(Node x, Node y) {
return Node(max(x.ma,y.ma),min(x.mi,y.mi));
}
void cons() {
for(int i = MAX/2-1;i>0;i--) {
seg[i] = f(seg[2*i],seg[2*i+1]);
}
}
Node sum(int s, int e, int n, int ns, int ne) {
if(e<=ns||ne<=s) return Node();
if(s<=ns&&ne<=e) return seg[n];
int mid = ns + ne >> 1;
return f(sum(s,e,2*n,ns,mid),sum(s,e,2*n+1,mid,ne));
}
Node sum(int s, int e) {
return sum(s, e, 1, 0, MAX/2);
}
int LeftSmall(int s, int e, int k) {
if(e == s + 1) {
if(seg[s+MAX/2].ma <= k) return s;
else return INF;
}
int mid = s + e >> 1;
if(sum(s,mid).mi <= k) return LeftSmall(s,mid,k);
return LeftSmall(mid,e,k);
}
int RightSmall(int s, int e, int k) {
if(e == s + 1) {
if(seg[s+MAX/2].ma <= k) return s;
else return -INF;
}
int mid = s + e >> 1;
if(sum(mid,e).mi <= k) return RightSmall(mid,e,k);
return RightSmall(s,mid,k);
}
int LeftBig(int s, int e, int k) {
if(e == s + 1) {
if(seg[s+MAX/2].ma >= k) return s;
else return INF;
}
int mid = s + e >> 1;
if(sum(s,mid).ma >= k) return LeftBig(s,mid,k);
return LeftBig(mid,e,k);
}
int RightBig(int s, int e, int k) {
if(e == s + 1) {
if(seg[s+MAX/2].ma >= k) return s;
else return -INF;
}
int mid = s + e >> 1;
if(sum(mid,e).ma >= k) return RightBig(mid,e,k);
return RightBig(s,mid,k);
}
};
vector<vector<int> > adj;
int A[200005];
int B[200005];
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R) {
vector<int> ans;
int Q = S.size();
int M = X.size();
adj.resize(N);
int i;
for(i=0;i<M;i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int st;
for(i=0;i<M;i++) {
if(adj[i].size()==1) st = i;
}
int p = -1, c = st;
i = 0;
while(i != N) {
A[i] = c;
B[c] = i;
for(int n : adj[c]) {
if(n != p) {
p = c;
c = n;
break;
}
}
i++;
}
//for(i=0;i<N;i++) cout << A[i] << ' ';
//cout << '\n';
SegTree tree(N+5);
int MAX = tree.MAX;
for(i=0;i<N;i++) {
tree.seg[i+MAX/2].ma = A[i];
tree.seg[i+MAX/2].mi = A[i];
}
tree.cons();
for(i=0;i<Q;i++) {
int x = B[S[i]];
int y = B[E[i]];
int l = L[i];
int r = R[i];
if(S[i] < L[i] || R[i] < E[i]) {
ans.push_back(0);
continue;
}
if(x < y) {
int k1 = tree.LeftSmall(x, y+1, l-1) - 1;
int k2 = tree.RightBig(x, y+1, r+1)+1;
//cout << x << ' ' << y << ' ' << k1 << ' ' << k2 << '\n';
if(k1 >= k2) ans.push_back(1);
else ans.push_back(0);
}
else {
int k1 = tree.LeftBig(y, x+1, r+1)-1;
int k2 = tree.RightSmall(y, x + 1, l-1) + 1;
//cout << x << ' ' << y << ' ' << k1 << ' ' << k2 << '\n';
if(k1 >= k2) ans.push_back(1);
else ans.push_back(0);
}
}
return ans;
}
Compilation message
werewolf.cpp: In member function 'SegTree::Node SegTree::sum(int, int, int, int, int)':
werewolf.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | int mid = ns + ne >> 1;
| ~~~^~~~
werewolf.cpp: In member function 'int SegTree::LeftSmall(int, int, int)':
werewolf.cpp:42:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int mid = s + e >> 1;
| ~~^~~
werewolf.cpp: In member function 'int SegTree::RightSmall(int, int, int)':
werewolf.cpp:51:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid = s + e >> 1;
| ~~^~~
werewolf.cpp: In member function 'int SegTree::LeftBig(int, int, int)':
werewolf.cpp:60:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int mid = s + e >> 1;
| ~~^~~
werewolf.cpp: In member function 'int SegTree::RightBig(int, int, int)':
werewolf.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = s + e >> 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:98:26: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
98 | for(int n : adj[c]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1808 ms |
27420 KB |
Output is correct |
| 2 |
Correct |
1969 ms |
35868 KB |
Output is correct |
| 3 |
Correct |
2044 ms |
36192 KB |
Output is correct |
| 4 |
Correct |
1962 ms |
35916 KB |
Output is correct |
| 5 |
Correct |
2012 ms |
35812 KB |
Output is correct |
| 6 |
Correct |
1885 ms |
35912 KB |
Output is correct |
| 7 |
Correct |
2017 ms |
35920 KB |
Output is correct |
| 8 |
Correct |
1987 ms |
35820 KB |
Output is correct |
| 9 |
Correct |
911 ms |
35836 KB |
Output is correct |
| 10 |
Correct |
1008 ms |
35828 KB |
Output is correct |
| 11 |
Correct |
1151 ms |
35968 KB |
Output is correct |
| 12 |
Correct |
1416 ms |
35924 KB |
Output is correct |
| 13 |
Correct |
1878 ms |
35852 KB |
Output is correct |
| 14 |
Correct |
1889 ms |
36000 KB |
Output is correct |
| 15 |
Correct |
1904 ms |
35920 KB |
Output is correct |
| 16 |
Correct |
1816 ms |
35876 KB |
Output is correct |
| 17 |
Correct |
1941 ms |
35948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
