#include "werewolf.h"
#include <iostream>
#include <assert.h>
#include <numeric>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
#define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
#define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
#define p(x) {}
#define p2(x,y) {}
#define pp(x) {}
#define pv(x) {}
#define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int NN = 3e5+1;
vector<vector<int> > a;
bool flag;
int mn[2][NN*4],mx[2][NN*4];
int arr[2][NN],posi[NN];
bool mt = false;
void buildmn(int s, int e, int idx){
if(s==e){
mn[mt][idx] = arr[mt][idx];
return;
}
int mid = (s+e)/2;
buildmn(s,mid,idx*2);
buildmn(mid+1,e,idx*2+1);
mn[mt][idx] = min(mn[mt][idx*2],mn[mt][idx*2+1]);
}
void buildmx(int s, int e, int idx){
if(s==e){
mx[mt][idx] = arr[mt][idx];
return;
}
int mid = (s+e)/2;
buildmx(s,mid,idx*2);
buildmx(mid+1,e,idx*2+1);
mx[mt][idx] = max(mx[mt][idx*2],mx[mt][idx*2+1]);
}
int lo(int s, int e, int idx, int l, int x){
if(e < l)return -1;
if(s==e){
assert(mn[mt][idx] < x);
return s;
}
int mid = (s+e)/2;
int res = -1;
if(mn[mt][idx*2] < x){
res = lo(s,mid,idx*2,l,x);
}
if(res == -1 && mn[mt][idx*2+1] < x){
res = lo(mid+1,e,idx*2+1,l,x);
}
return res;
}
int hi(int s, int e, int idx, int l, int x){
if(e < l)return -1;
if(s == e){
assert(mx[mt][idx] > x);
return s;
}
int mid = (s+e)/2;
int res = -1;
if(mx[mt][idx*2] > x){
res = hi(s,mid,idx*2,l,x);
}
if(res == -1 && mx[mt][idx*2+1] > x){
res = hi(mid+1,e,idx*2+1,l,x);
}
return res;
}
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) {
//arr.resize(N);
a.assign(N,vector<int>());
int q = S.size();
int m = X.size();
int i,k;
for(i=0;i<m;i++){
int x = X[i], y = Y[i];
a[x].push_back(y);
a[y].push_back(x);
}
int x = -1;
for(i=0;i<N;i++){
if(a[i].size() == 1)x = i;
}
assert(x != -1);
assert(mt == false);
arr[mt][0] = x;
int y = x;
x = a[x][0];
for(i=1;i<N-1;i++){
arr[mt][i] = x;
if(a[x][0] == y){
y = x;
x = a[x][1];
}
else{
y = x;
x = a[x][0];
}
}
arr[mt][N-1] = x;
assert(a[x].size()==1);
for(i=0;i<N;i++){
arr[mt^1][i] = arr[mt][N-i-1];
posi[arr[mt][i]] = i;
}
vector<int> ans;
buildmx(0,N-1,1);
buildmn(0,N-1,1);
mt ^= 1;
//reverse(all(arr));
buildmx(0,N-1,1);
buildmn(0,N-1,1);
mt ^= 1;
//reverse(all(arr));
for(k=0;k<q;k++){
int s = S[k], e = E[k];
int l = L[k];
int r = R[k];
if(posi[s] < posi[e])
mt = true;
else
mt = false;
int idx = lo(0,N-1,1,s,l);
if(idx == -1 || idx > e){
ans.push_back(true);
continue;
}
if(arr[mt][idx-1] > r){
ans.push_back(false);
continue;
}
idx = hi(0,N-1,1,idx,r);
if(idx == -1 || idx > e){
ans.push_back(true);
// continue;
}
else{
ans.push_back(false);
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
291 ms |
32408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
