#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define REP(i, a, b) for (ll i=a; i<b; i++)
#define pb push_back
int ordem[200000];
vector<int> graph[200000];
int seg_tree_maximo[800000];
int seg_tree_minimo[800000];
int posicao[200000];
void create (int i, int minimo, int maximo)
{
if (minimo == maximo)
{
seg_tree_maximo[i] = ordem[minimo];
seg_tree_minimo[i] = ordem[minimo];
return;
}
int med = (minimo + maximo)/2;
create (2*i+1, minimo, med);
create (2*i+2, med+1, maximo);
seg_tree_maximo[i] = max (seg_tree_maximo[2*i+1], seg_tree_maximo[2*i+2]);
seg_tree_minimo[i] = min (seg_tree_minimo[2*i+1], seg_tree_minimo[2*i+2]);
return;
}
int minimizar (int i, int minimo, int maximo, int menor, int maior)
{
if (minimo == menor && maximo == maior)
return seg_tree_minimo[i];
int med = (minimo + maximo)/2;
if (maior <= med)
return minimizar(2*i+1, minimo, med, menor, maior);
if (menor > med)
return minimizar(2*i+2, med+1, maximo, menor, maior);
return min (minimizar(2*i+1, minimo, med, menor, med), minimizar(2*i+2, med+1, maximo, med+1, maximo));
}
int maximizar (int i, int minimo, int maximo, int menor, int maior)
{
if (minimo == menor && maximo == maior)
return seg_tree_maximo[i];
int med = (minimo + maximo)/2;
if (maior <= med)
return maximizar(2*i+1, minimo, med, menor, maior);
if (menor > med)
return maximizar(2*i+2, med+1, maximo, menor, maior);
return min (maximizar(2*i+1, minimo, med, menor, med), maximizar(2*i+2, med+1, maximo, med+1, maximo));
}
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)
{
int Q = S.size();
vector<int> ans(Q);
REP(i, 0, (int)X.size())
{
graph[X[i]].pb (Y[i]);
graph[Y[i]].pb (X[i]);
}
REP(i, 0, N)
{
if ((int)graph[i].size() == 1)
{
ordem[0] = i;
posicao[i] = 0;
break;
}
}
ordem[1] = graph[ordem[0]][0];
posicao[ordem[1]] = 1;
REP(i, 2, N)
{
if (graph[ordem[i-1]][0] == ordem[i-2])
ordem[i] = graph[ordem[i-1]][1];
else
ordem[i] = graph[ordem[i-1]][0];
posicao[ordem[i]] = i;
}
create(0, 0, N-1);
REP(i, 0, Q)
{
int inicio = posicao[S[i]];
int fim = posicao[E[i]];
if (S[i] < L[i] || E[i] > R[i])
{
ans[i] = 0;
continue;
}
if (inicio < fim)
{
int minimo = inicio, maximo = fim;
while (minimo != maximo)
{
int med = (minimo + maximo + 1)/2;
if (minimizar(0, 0, N-1, inicio, med) < L[i])
maximo = med - 1;
else
minimo = med;
}
if (maximizar(0, 0, N-1, minimo, fim) > R[i])
ans[i] = 0;
else
ans[i] = 1;
}
else
{
int minimo = fim, maximo = inicio;
while (minimo != maximo)
{
int med = (minimo + maximo + 1)/2;
if (minimizar(0, 0, N-1, med, inicio) < L[i])
minimo = med + 1;
else
maximo = med;
}
if (maximizar(0, 0, N-1, fim, minimo) > R[i])
ans[i] = 0;
else
ans[i] = 1;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4045 ms |
4940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4045 ms |
4940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4050 ms |
27120 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4045 ms |
4940 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
