#include "plants.h"
#include <bits/stdc++.h>
#include <random>
#include <type_traits>
using namespace std;
/*
* Si h[i] < h[i+1], alors r[i+1] <= r[i]
* Si h[i] > h[i+1] alors r[i+1] >= r[i]
* Donc si on a r[i] != r[i+1] on peut comparer r[i] et r[i+1] !
* r[i+1] > r[i] => h[i+1] < h[i]
* r[i+1] < r[i] => h[i+1] > h[i]
* 1 : AC
* 2 : AC
* 3 : AC
* 4 : AC
* 5 : AC
* 6 : AC
* 7 : NA
*
* If can build graph efficiently then ez !
*/
const int MAXN = 2e5;
const int MAXP = 18;
int k;
int lftEdge[MAXN][MAXP], rgtEdge[MAXN][MAXP];
int nbPlusGrands[MAXN];
bool reach[301][301];
vector<int> order;
int nbPlantes;
struct Seg {
int nbValeurs;
vector<int> order;
vector<int> valeurs;
vector<int> iDeb, iFin, lazy, minVal;
const int INF = 1e9;
Seg(vector<int> _v) : nbValeurs(_v.size()), valeurs(_v) {
int p = 0;
while ((1 << p) < nbValeurs)
++p;
int x = 2 * (1 << p) + 1;
iDeb.resize(x), iFin.resize(x), lazy.resize(x), minVal.resize(x);
buildTree(1, 0, nbValeurs - 1);
while ((int)order.size() < nbValeurs)
getNxt();
}
void pull(int iNoeud) {
minVal[iNoeud] = min(minVal[2 * iNoeud], minVal[2 * iNoeud + 1]);
}
void push(int iNoeud) {
if (!lazy[iNoeud])
return;
minVal[iNoeud] += lazy[iNoeud];
if (iDeb[iNoeud] < iFin[iNoeud]) {
lazy[2 * iNoeud] += lazy[iNoeud];
lazy[2 * iNoeud + 1] += lazy[iNoeud];
}
lazy[iNoeud] = 0;
}
void buildTree(int iNoeud, int deb, int fin) {
iDeb[iNoeud] = deb, iFin[iNoeud] = fin;
if (deb == fin) {
minVal[iNoeud] = valeurs[deb];
return;
}
buildTree(2 * iNoeud, deb, (deb + fin) / 2);
buildTree(2 * iNoeud + 1, (deb + fin) / 2 + 1, fin);
pull(iNoeud);
}
void decrement(int iNoeud, int deb, int fin) {
push(iNoeud);
if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
return;
if (deb <= iDeb[iNoeud] and iFin[iNoeud] <= fin) {
lazy[iNoeud]--;
push(iNoeud);
return;
}
decrement(2 * iNoeud, deb, fin);
decrement(1 + 2 * iNoeud, deb, fin);
pull(iNoeud);
}
int findFirstZero(int iNoeud, int deb, int fin) {
push(iNoeud);
if (minVal[iNoeud] or iDeb[iNoeud] > fin or iFin[iNoeud] < deb)
return -1;
if (iDeb[iNoeud] == iFin[iNoeud])
return iDeb[iNoeud];
int retLft = findFirstZero(2 * iNoeud, deb, fin);
if (retLft != -1)
return retLft;
return findFirstZero(2 * iNoeud + 1, deb, fin);
}
void delVal(int iNoeud, int pos) {
push(iNoeud);
if (iDeb[iNoeud] > pos or iFin[iNoeud] < pos)
return;
if (iDeb[iNoeud] == iFin[iNoeud]) {
minVal[iNoeud] = INF;
return;
}
delVal(2 * iNoeud, pos);
delVal(2 * iNoeud + 1, pos);
pull(iNoeud);
}
int findZeroBefore(int pos) {
int posAvant = pos - k + 1;
if (posAvant >= 0)
return findFirstZero(1, posAvant, pos - 1);
else {
posAvant += nbValeurs;
int ret = findFirstZero(1, posAvant, nbValeurs - 1);
if (ret == -1 and pos)
ret = findFirstZero(1, 0, pos - 1);
return ret;
}
}
void get(int pos) {
// cout << "EXTRACTING " << pos << endl;
while (true) {
int x = findZeroBefore(pos);
if (x == -1)
break;
get(x);
}
order.push_back(pos);
int posAvant = pos - k + 1;
delVal(1, pos);
if (pos)
decrement(1, max(0, posAvant), pos - 1);
if (posAvant < 0)
decrement(1, posAvant + nbValeurs, nbValeurs - 1);
// cout << "EXTRACTED " << pos << endl;
}
void getNxt() {
int posZero = findFirstZero(1, 0, nbValeurs - 1);
assert(posZero != -1);
get(posZero);
}
};
int disCircle(int x, int y) {
if (x < y)
return y - x;
return nbPlantes - x + y;
}
struct segMax {
vector<pair<int, int>> seg;
int deb = 0, p = 0;
segMax(int n) {
while ((1 << p) < n)
++p;
deb = 1 << p;
seg.assign(2 * deb + 1, make_pair(-1, n));
}
void upd(int i, int v) {
i += deb;
seg[i] = make_pair(v, i - deb);
while (i > 1) {
i /= 2;
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
}
int query(int l, int r) {
pair<int, int> ret(-1, nbPlantes);
l += deb, r += deb;
while (l < r) {
if (l % 2)
ret = max(ret, seg[l++]);
if (r % 2 == 0)
ret = max(ret, seg[r--]);
l /= 2, r /= 2;
}
if (l == r)
ret = max(ret, seg[l]);
return ret.second;
}
};
void init(int _k, vector<int> r) {
k = _k;
nbPlantes = r.size();
for (int iPlante = 0; iPlante < nbPlantes; ++iPlante) {
nbPlusGrands[iPlante] = r[iPlante];
}
Seg s(r);
order.resize(nbPlantes + 1);
for (int i = 0; i < nbPlantes; ++i)
order[s.order[i]] = nbPlantes - 1 - i;
order[nbPlantes] = -1;
segMax seg(nbPlantes);
reverse(s.order.begin(), s.order.end());
for (int i : s.order) {
int ret1 = nbPlantes, ret2 = nbPlantes;
if (i) {
ret1 = seg.query(max(0, i - k + 1), i - 1);
}
if (i - k + 1 < 0) {
ret2 = seg.query(i - k + 1 + nbPlantes, nbPlantes - 1);
}
if (order[ret1] > order[ret2]) {
lftEdge[i][0] = ret1;
} else {
lftEdge[i][0] = ret2;
}
ret1 = ret2 = nbPlantes;
if (i < nbPlantes - 1)
ret1 = seg.query(i + 1, min(nbPlantes - 1, i + k - 1));
if (i + k - 1 > nbPlantes)
ret2 = seg.query(0, i + k - 1 - nbPlantes);
if (order[ret1] > order[ret2])
rgtEdge[i][0] = ret1;
else
rgtEdge[i][0] = ret2;
seg.upd(i, order[i]);
}
lftEdge[nbPlantes][0] = rgtEdge[nbPlantes][0] = nbPlantes;
for (int p = 0; p + 1 < MAXP; ++p)
for (int i = 0; i <= nbPlantes; ++i) {
lftEdge[i][p + 1] = lftEdge[lftEdge[i][p]][p];
rgtEdge[i][p + 1] = rgtEdge[rgtEdge[i][p]][p];
}
}
int goRight(int x, int d) {
for (int p = MAXP - 1; p >= 0; --p) {
int y = rgtEdge[x][p];
int dis = (y - x + nbPlantes) % nbPlantes;
if (dis <= d)
d -= dis, x = y;
}
return x;
}
int goLeft(int x, int d) {
for (int p = MAXP - 1; p >= 0; --p) {
int y = lftEdge[x][p];
if (y == nbPlantes)
continue;
int dis = (x - y + nbPlantes) % nbPlantes;
if (dis <= d)
d -= dis, x = y;
}
return x;
}
bool isGreater(int x, int y) { // x > y ?
int d1 = (y - x + nbPlantes) % nbPlantes;
int d2 = (x - y + nbPlantes) % nbPlantes;
int x1 = goRight(x, d1), x2 = goLeft(x, d2);
if ((y - x1 + nbPlantes) % nbPlantes < k and order[x1] >= order[y])
return true;
if ((x2 - y + nbPlantes) % nbPlantes < k and order[x2] >= order[y])
return true;
return false;
}
int compare_plants(int x, int y) {
if (isGreater(x, y))
return 1;
if (isGreater(y, x))
return -1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
216 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
115 ms |
3040 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
132 ms |
3564 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
216 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
115 ms |
3040 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
