제출 #1031385

#제출 시각아이디문제언어결과실행 시간메모리
10313850pt1mus23늑대인간 (IOI18_werewolf)C++14
0 / 100
365 ms524288 KiB
#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 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]; void dfs(int node,int par=-1){ idx[node]=arr.size(); arr.pb(node); for(auto v:graph[node]){ if(v!=par){ dfs(v,node); } } } 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<sze;i++){ lg[i]=lg[i/2]+1; } vector<int> A(Q); int m = X.size(); 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; } } dfs(x); 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 { min(dpmn[len][l],dpmn[len][r - (1<<len)+1]), max(dpmx[len][l],dpmx[len][r - (1<<len)+1])}; }; auto qry2 = [&](int l,int r) -> pii { int len =lg[r-l+1]; return { min(dpmn2[len][l],dpmn2[len][r - (1<<len)+1]), 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 l,r,ans = -1; if(idx[start]<idx[finish]){ l = idx[start]; r = idx[finish]; while(l<=r){ int mid = (l+r)/2; pii res = qry(idx[start],mid); if(res.second <= wr){ l=mid+1; ans=max(ans,mid); } else{ r=mid-1; } } if(ans!=-1 && qry(ans,idx[finish]).first>=wl && arr[ans]>=wl && arr[ans]<=wr){ A[i]=1; } } else{ // reverse l = idx2[start]; r = idx2[finish]; while(l<=r){ int mid = (l+r)/2; pii res = qry2(idx2[start],mid); if(res.second <= wr){ l=mid+1; ans=max(ans,mid); } else{ r=mid-1; } } if(ans!=-1 && qry2(ans,idx2[finish]).first>=wl && arr2[ans]>=wl && arr2[ans]<=wr){ A[i]=1; } } } return A; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...