This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 3e2;
#define MP make_pair
#define PII pair<int, int>
vector<int> g[MAXN];
bool used[MAXN];
int tin[MAXN];
vector<int> vec = {0};
void dfs(int v){
used[v] = true;
tin[v] = vec.size();
vec.push_back(v);
for (int u : g[v]){
if (!used[u]){
dfs(u);
}
}
}
PII t[MAXN][20];
int Log[MAXN];
PII combine(PII lf, PII rg){
return MP(min(lf.first, rg.first), max(lf.second, rg.second));
}
void build(int n){
Log[1] = 0;
for (int i = 2; i <= n; i++) Log[i] = Log[i / 2] + 1;
for (int i = 0; i < 20; i++){
for (int j = 1; j <= n; j++){
if (i == 0){
t[j][i] = MP(vec[j], vec[j]);
} else {
if (j + (1 << (i - 1)) < MAXN) t[j][i] = combine(t[j][i - 1], t[j + (1 << (i - 1))][i - 1]);
}
}
}
}
PII get(int l, int r){
if (l > r) return MP(1e9, -1e9);
if (l == r) return t[l][0];
int x = Log[r - l + 1];
PII res = combine(t[l][x], t[r - (1 << x) + 1][x]);
return res;
}
PII get_positions(int X, int N, int L, int R){
X = tin[X];
int lf = X, rg = X;
int l = 1, r = X;
while (l <= r){
int m = (l + r) >> 1;
PII f = get(m, X);
if (f.first >= L && f.second <= R){
lf = m;
r = m - 1;
} else l = m + 1;
}
l = X, r = N;
while (l <= r){
int m = (l + r) >> 1;
PII f = get(X, m);
if (f.first >= L && f.second <= R){
rg = m;
l = m + 1;
} else r = m - 1;
}
return MP(lf, rg);
}
int smaller[MAXN];
int fw[MAXN];
void add(int x, int y){
while (x < MAXN){
fw[x] += y;
x += (-x & x);
}
}
int get(int x){
int ret = 0;
while (x > 0){
ret += fw[x];
x -= (-x & x);
}
return ret;
}
vector<pair<PII, PII>> queries[MAXN];
void dfs2(int v, int l, int r, vector<bool> &used){
used[v] = true;
for (int u : g[v]){
if (!used[u] && l <= u && u <= r){
dfs2(u, l, r, used);
}
}
}
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(), M = X.size();
vector<int> A(Q, 0);
for (int i = 0; i < M; i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
if (N <= 3000 && M <= 6000 && Q <= 3000){
for (int i = 0; i < Q; i++){
vector<bool> used1(N, false), used2(N, false);
dfs2(S[i], L[i], N - 1, used1);
dfs2(E[i], 0, R[i], used2);
for (int j = L[i]; j <= R[i]; j++){
if (used1[j] && used2[j]) A[i] = 1;
}
}
return A;
}
for (int i = 0; i < N; i++){
if (g[i].size() == 1){
dfs(i);
break;
}
}
build(N);
for (int i = 0; i < Q; i++){
PII fs = get_positions(S[i], N, L[i], N - 1), fe = get_positions(E[i], N, 0, R[i]);
int l1 = fs.first, r1 = fs.second, l2 = fe.first, r2 = fe.second;
//cout << "\t" << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;
int l = max(l1, l2), r = min(r1, r2);
if (L[i]) queries[L[i] - 1].emplace_back(MP(i, 0), MP(l, r));
queries[R[i]].emplace_back(MP(i, 1), MP(l, r));
}
//return A;
for (int i = 0; i < N; i++){
add(tin[i], 1);
for (auto qu : queries[i]){
int ind = qu.first.first, ty = qu.first.second, l = qu.second.first, r = qu.second.second;
// cout << i << ' ' << l << ' ' << r << endl;
int res = get(r) - get(l - 1);
if (ty == 0) A[ind] -= res; else
A[ind] += res;
}
}
for (int i = 0; i < Q; i++) A[i] = A[i] > 0;
return A;
}
/**
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
6 5 1
2 0
0 1
3 5
1 3
5 4
1 4 0 4
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |