제출 #116288

#제출 시각아이디문제언어결과실행 시간메모리
116288mirbek01늑대인간 (IOI18_werewolf)C++11
0 / 100
863 ms67504 KiB
# include <bits/stdc++.h> # include "werewolf.h" using namespace std; const int N = 4e5 + 2; int ver[N], pos[N], n, t[2][18][N], lg[N]; vector <int> g[N]; int get(int l, int r, int tp){ // if(tl > r || l > tr){ // if(tp) // return 0; // else // return 2e9; // } // if(l <= tl && tr <= r) // return t[tp][v]; // int tm = (tl + tr) >> 1; // if(tp) // return max(get(l, r, tp, v << 1, tl, tm), // get(l, r, tp, v << 1 | 1, tm + 1, tr)); // else // return min(get(l, r, tp, v << 1, tl, tm), // get(l, r, tp, v << 1 | 1, tm + 1, tr)); int curlog = lg[r - l + 1]; if(tp) return max(t[1][curlog][l], t[1][curlog][r - (1 << curlog) + 1]); else return min(t[0][curlog][l], t[1][curlog][r - (1 << curlog) + 1]); } void dfs(int v, int par = -1){ ver[++ n] = v; for(int to : g[v]){ if(to == par) continue; dfs(to, v); } } 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(); int m = X.size(); vector <int> A(q); for(int i = 0; i < m; i ++){ g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]); } for(int i = 0; i < N; i ++){ if(g[i].size() == 1){ dfs(i); break; } } for(int i = 1; i <= n; i ++){ pos[ver[i]] = i; } for(int i = 2; i <= n; i ++) lg[i] = lg[i / 2] + 1; for(int i = 0; i <= lg[n]; i ++){ if(!i){ for(int j = 1; j <= n; j ++) t[0][i][j] = ver[j], t[1][i][j] = ver[j]; } else { int curlen = 1 << (i - 1); for(int j = 1; j <= n; j ++){ t[0][i][j] = min(t[0][i - 1][j], t[0][i - 1][min(n, j + curlen)]), t[1][i][j] = max(t[1][i - 1][j], t[1][i - 1][min(n, j + curlen)]); } } } for(int i = 0; i < q; i ++){ int l1, l2, r1, r2; l1 = pos[S[i]], r1 = pos[S[i]]; l2 = pos[E[i]], r2 = pos[E[i]]; int lo = 1, hi = l1, ret = l1; while(lo <= hi){ int md = (lo + hi) >> 1; if(get(md, l1, 0) >= L[i]) hi = md - 1, ret = md; else lo = md + 1; } l1 = ret; lo = r1, hi = n; while(lo <= hi){ int md = (lo + hi) >> 1; if(get(r1, md, 0) >= L[i]) lo = md + 1, ret = md; else hi = md - 1; } r1 = ret; lo = 1, hi = l2, ret = l2; while(lo <= hi){ int md = (lo + hi) >> 1; if(get(md, l2, 1) <= R[i]) hi = md - 1, ret = md; else lo = md + 1; } l2 = ret; lo = r2, hi = n; while(lo <= hi){ int md = (lo + hi) >> 1; if(get(r2, md, 1) <= R[i]) lo = md + 1, ret = md; else hi = md - 1; } r2 = ret; if(max(l1, l2) <= min(r1, r2)) 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...