#include "island.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100100;
const int BSIZE = 500;
const int NBUCK = 210;
int N, M;
int fval[MAXN];
vector <int> floc[MAXN];
int par[MAXN];
vector <int> guys[MAXN];
vector <int> dists[MAXN];
int ndist[MAXN];
int oloc[MAXN];
int nmin[MAXN][22];
void uni (int left, int right, int now)
{
left = par[left];
right = par[right];
if (left == right) return;
if (guys[left].size() < guys[right].size()) swap (left, right);
dists[left].push_back(now);
for (int guy : guys[right])
{
guys[left].push_back(guy);
par[guy] = left;
}
for (int dist : dists[right])
{
dists[left].push_back(dist);
}
guys[right].clear();
dists[right].clear();
}
int nbig;
vector <int> bfinch;
int bloc[MAXN];
int bdist[NBUCK];
int bbest[NBUCK][MAXN];
void Init(int K, std::vector<int> F, std::vector<int> S, std::vector<int> E){
N = F.size(), M = S.size();
for (int i = 0; i < N; i++)
{
fval[i] = F[i];
floc[fval[i]].push_back(i);
}
for (int i = 0; i < N; i++)
{
guys[i].clear();
dists[i].clear();
guys[i].push_back(i);
par[i] = i;
}
for (int i = M - 1; i >= 0; i--)
{
int l = S[i], r = E[i];
uni (l, r, i + 1);
}
int cp = par[0];
for (int i = 0; i < N; i++)
{
if (i < N - 1)
ndist[i] = dists[cp][i];
oloc[guys[cp][i]] = i;
}
nbig = 0;
for (int i = 0; i <= N; i++)
{
if (!floc[i].size()) continue;
for (int j = 0; j < floc[i].size(); j++)
floc[i][j] = oloc[floc[i][j]];
sort (floc[i].begin(), floc[i].end());
if (floc[i].size() >= BSIZE)
{
bfinch.push_back(i);
bloc[i] = nbig;
nbig++;
}
else
bloc[i] = -1;
}
for (int i = 0; i < nbig; i++)
{
bdist[i] = -1;
for (int j = 0; j < MAXN; j++)
bbest[i][j] = -1;
}
for (int i = 0; i < N; i++)
{
int ccolor = fval[guys[cp][i]];
for (int j = 0; j < nbig; j++)
bbest[j][ccolor] = max (bbest[j][ccolor], bdist[j]);
if (bloc[ccolor] != -1)
bdist[bloc[ccolor]] = 1e9;
if (i == N - 1) continue;
for (int j = 0; j < nbig; j++)
bdist[j] = min (bdist[j], ndist[i]);
}
for (int i = 0; i < nbig; i++)
{
bdist[i] = -1;
}
for (int i = N - 1; i >= 0; i--)
{
int ccolor = fval[guys[cp][i]];
for (int j = 0; j < nbig; j++)
bbest[j][ccolor] = max (bbest[j][ccolor], bdist[j]);
if (bloc[ccolor] != -1)
bdist[bloc[ccolor]] = 1e9;
if (i == 0) continue;
for (int j = 0; j < nbig; j++)
bdist[j] = min (bdist[j], ndist[i-1]);
}
for (int i = 0; i < N; i++)
nmin[i][0] = ndist[i];
for (int a = 0; a < 19; a++)
{
for (int i = 0; i < N; i++)
{
nmin[i][a+1] = nmin[i][a];
if (i + (1 << a) < N)
nmin[i][a+1] = min (nmin[i][a], nmin[i+(1<<a)][a]);
}
}
}
int gogo (int x, int y)
{
//cout << "go " << x << " " << y << endl;
if (x > y) swap (x, y);
if (x == y) return 1e9;
//cout << "gogo " << x << " " << y << "\n";
int np = 31 - __builtin_clz(y - x);
return min (nmin[x][np], nmin[y-(1<<np)][np]);
}
int Separate(int A, int B)
{
//cout << "YO\n";
/*if (bloc[A] != -1)
return bbest[bloc[A]][B];
if (bloc[B] != -1)
return bbest[bloc[B]][A];*/
vector <int> l = floc[A], r = floc[B];
//return gogo (l[0], r[0]);
int lloc = 0, rloc = 0;
int ans = -1;
while (lloc < l.size() && rloc < r.size())
{
ans = max (ans, gogo (l[lloc], r[rloc]));
if (l[lloc] < r[rloc])
lloc++;
else
rloc++;
}
return ans;
}
Compilation message
island.cpp: In function 'void Init(int, std::vector<int>, std::vector<int>, std::vector<int>)':
island.cpp:84:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < floc[i].size(); j++)
~~^~~~~~~~~~~~~~~~
island.cpp: In function 'int Separate(int, int)':
island.cpp:169:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (lloc < l.size() && rloc < r.size())
~~~~~^~~~~~~~~~
island.cpp:169:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (lloc < l.size() && rloc < r.size())
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
253 ms |
32740 KB |
Output is correct |
| 2 |
Correct |
241 ms |
32740 KB |
Output is correct |
| 3 |
Correct |
257 ms |
32736 KB |
Output is correct |
| 4 |
Correct |
247 ms |
32484 KB |
Output is correct |
| 5 |
Correct |
274 ms |
32740 KB |
Output is correct |
| 6 |
Correct |
285 ms |
32740 KB |
Output is correct |
| 7 |
Correct |
258 ms |
32740 KB |
Output is correct |
| 8 |
Correct |
277 ms |
32740 KB |
Output is correct |
| 9 |
Correct |
275 ms |
32740 KB |
Output is correct |
| 10 |
Correct |
243 ms |
32740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 3 |
Execution timed out |
5099 ms |
30436 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7424 KB |
Output is correct |
| 3 |
Correct |
253 ms |
32740 KB |
Output is correct |
| 4 |
Correct |
241 ms |
32740 KB |
Output is correct |
| 5 |
Correct |
257 ms |
32736 KB |
Output is correct |
| 6 |
Correct |
247 ms |
32484 KB |
Output is correct |
| 7 |
Correct |
274 ms |
32740 KB |
Output is correct |
| 8 |
Correct |
285 ms |
32740 KB |
Output is correct |
| 9 |
Correct |
258 ms |
32740 KB |
Output is correct |
| 10 |
Correct |
277 ms |
32740 KB |
Output is correct |
| 11 |
Correct |
275 ms |
32740 KB |
Output is correct |
| 12 |
Correct |
243 ms |
32740 KB |
Output is correct |
| 13 |
Execution timed out |
5099 ms |
30436 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
