#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 1e18;
int n, m, q, k;
vector<vector<int>> v;
vector <pair<int, int>> se;
vector <pair<int, int>> lr;
vector <ll> mx, mn;
vector <ll> sth, inx;
void upd(int in, ll x){
in+=k/2;
mx[in] = x, mn[in] = x, in/=2;
while(in > 0){
mx[in] = max(mx[2*in], mx[2*in+1]);
mn[in] = min(mn[2*in], mn[2*in+1]);
in/=2;
}
}
ll smx(int l, int r){
l+=k/2, r+=k/2;
ll s = -inf;
while(l <= r){
if(l%2 == 1) s = max(s, mx[l]), l++;
if(r%2 == 0) s = max(s, mx[r]), r--;
l/=2, r/=2;
}
return s;
}
ll smn(int l, int r){
l+=k/2, r+=k/2;
ll s = inf;
while(l <= r){
if(l%2 == 1) s = min(s, mn[l]), l++;
if(r%2 == 0) s = min(s, mn[r]), r--;
l/=2, r/=2;
}
return s;
}
ll gmx(int a, int b, ll x){
int rr = -1;
if(smx(a, b) <= x) return rr;
while(1){
if(b - a < 2){
if(smx(a, a) > x) rr = a;
else rr = b;
break;
}
int md = (a+b)/2;
if(smx(a, md) > x) b = md;
else a = md+1;
}
return rr;
}
ll gmn(int a, int b, ll x){
int rr = -1;
if(smn(a, b) >= x) return rr;
while(1){
if(b - a < 2){
if(smn(b, b) < x) rr = a;
else rr = a;
break;
}
int md = (a+b)/2;
if(smn(md, b) < x) a = md;
else b = md-1;
}
return rr;
}
ll rgmx(int a, int b, ll x){
int rr = -1;
if(smx(a, b) <= x) return rr;
while(1){
if(b - a < 2){
if(smx(b, b) > x) rr = a;
else rr = a;
break;
}
int md = (a+b)/2;
if(smx(md, b) > x) a = md;
else b = md-1;
}
return rr;
}
ll rgmn(int a, int b, ll x){
int rr = -1;
if(smn(a, b) >= x) return rr;
while(1){
if(b - a < 2){
if(smn(a, a) < x) rr = a;
else rr = b;
break;
}
int md = (a+b)/2;
if(smn(a, md) < x) b = md;
else a = md+1;
}
return rr;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
n = N, m = X.size(), q = S.size();
for(int i = 0; i < q; i++){
se.pb({S[i], E[i]});
lr.pb({L[i], R[i]});
}
v = vector<vector<int>>(n);
for(int i = 0; i < m; i++){
v[X[i]].pb(Y[i]);
v[Y[i]].pb(X[i]);
}
//-----main
int a = -1;
for(int i = 0; i < n; i++) if(v[i].size() == 1){
a = i;
break;
}
k = 1;
while(k <= n) k*=2;
k*=2;
sth.pb(a);
mx = vector<ll> (k, 0);
mn = mx;
int ls = -1, aa = a;
while(v[aa].size() > 1 || aa == a){
for(int x: v[aa]) if(x != ls){
ls = aa;
aa = x;
sth.pb(aa);
break;
}
}
inx = sth;
for(int i = 0; i < n; i++){
upd(i, sth[i]);
inx[sth[i]] = i;
}
vector<int> ans(q);
for(int i = 0; i < q; i++){
int s = se[i].f, e = se[i].sc, l = lr[i].f, r = lr[i].sc;
int ss = inx[s], ee =inx[e];
if(s < l) ans[i] = 0;
else if(e > r) ans[i] = 0;
else if(ss > ee){
int a = gmx(ee, ss, r), b = gmn(ee, ss, l);
if(a == -1 || b == -1) ans[i] = 1;
else if(b - a < 1) ans[i] = 0;
else ans[i] = 1;
}
else{
int a = rgmx(ss, ee, r), b = rgmn(ss, ee, l);
if(a == -1 || b == -1) ans[i] = 1;
else if(a - b < 1) ans[i] = 0;
else ans[i] = 1;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1291 ms |
36136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
