#include "werewolf.h"
#pragma GCC optimize("O3", "inline")
#define skillissue <bits/stdc++.h>
#define ultra_mal std
#include skillissue
using namespace ultra_mal;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ins insert
#define pb push_back
#define pii pair<int, int>
#define all(x) x.begin(),x.end()
#define hash FhashF
const int mod = 1e9 +7, sze = 2e5 +300, inf = INT_MAX, P = 1453;
vector<int> graph[sze];
vector<int> arr,arr2;
int par[sze];
int idx[sze],idx2[sze];
const int L = 20;
int lg[sze];
int dpmx[L][sze],dpmn[L][sze];
int dpmx2[L][sze],dpmn2[L][sze];
vector<int> check_validity(int n,vector<int> X,vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R){
int Q = S.size();
for(int i=2;i<=n+10;i++){
lg[i]=lg[i/2]+1;
}
vector<int> A(Q);
int m = X.size();
for(int i=0;i<n;i++){
par[i]=-1;
}
for(int i=0;i<m;i++){
graph[X[i]].pb(Y[i]);
graph[Y[i]].pb(X[i]);
}
int x =0;
for(int i =0;i<n;i++){
if(graph[i].size()==1){
x=i;
break;
}
}
queue<int> q;
q.push(x);
while(!q.empty()){
int node = q.front();q.pop();
idx[node]=arr.size();
arr.pb(node);
for(auto v:graph[node]){
if(par[node]!=v){
par[v]=node;
q.push(v);
}
}
}
arr2=arr;
int j= 0;
reverse(all(arr2));
for(auto v:arr2){
idx2[v]=j++;
}
j=0;// fobi
for(int i=0;i<n;i++){
dpmn[0][i]=arr[i];
dpmx[0][i]=arr[i];
dpmn2[0][i]=arr2[i];
dpmx2[0][i]=arr2[i];
}
for(int i=1;i<20;i++){
for(int j=0;j + (1<<i)<=n;j++){
dpmn[i][j]= min(dpmn[i-1][j],dpmn[i-1][j + (1<<(i-1))]);
dpmx[i][j]= max(dpmx[i-1][j],dpmx[i-1][j + (1<<(i-1))]);
dpmn2[i][j]= min(dpmn2[i-1][j],dpmn2[i-1][j + (1<<(i-1))]);
dpmx2[i][j]= max(dpmx2[i-1][j],dpmx2[i-1][j + (1<<(i-1))]);
}
}
auto qry = [&](int l,int r) -> pii {
int len =lg[r-l+1];
return { (int)min(dpmn[len][l],dpmn[len][r - (1<<len)+1]), (int)max(dpmx[len][l],dpmx[len][r - (1<<len)+1])};
};
auto qry2 = [&](int l,int r) -> pii {
int len =lg[r-l+1];
return { (int)min(dpmn2[len][l],dpmn2[len][r - (1<<len)+1]), (int)max(dpmx2[len][l],dpmx2[len][r - (1<<len)+1])};
};
for (int i = 0; i < Q; ++i) {
A[i] = 0;
int start = S[i];
int finish = E[i];
int wl = L[i];
int wr = R[i];
int md = -1;
int l =idx[start];
int r = idx[finish];
int sdx = idx[start];
int fdx = idx[finish];
if(sdx<fdx){
while(l<=r){
int mid = (l+r)/2;
/*
l->mid , hamisi <wl olmali
*/
pii res = qry(sdx,mid);
if(res.second <=wr && res.first<=wl){
md = mid;
l=mid+1;
}
else{
r= mid-1;
}
}
// cout<<sdx<<" "<<fdx<<" "<<md<<endl;
if(md!=-1){
pii resleft = qry(sdx,md);
pii resright = qry(min(fdx,md+1),fdx);
if(resleft.second <= wr && resright.first>=wl && arr[md]>=wl && arr[md]<=wr){
A[i]=1;
}
}
}
else{
l =idx2[start];
r = idx2[finish];
sdx = idx2[start];
fdx = idx2[finish];
while(l<=r){
int mid = (l+r)/2;
/*
l->mid , hamisi <wl olmali
*/
pii res = qry2(sdx,mid);
if(res.second <=wr && res.first<=wl){
md = mid;
l=mid+1;
}
else{
r= mid-1;
}
}
// cout<<sdx<<" "<<fdx<<" "<<md<<endl;
// int c = 0;
if(md!=-1){
pii resleft = qry2(sdx,md);
pii resright = qry2(min(fdx,md+1),fdx);
if(resleft.second <= wr && resright.first>=wl && arr2[md]>=wl && arr2[md]<=wr){
A[i]=1;
}
}
}
}
return A;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
922 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
922 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
248 ms |
88772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
922 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
