oj.uz

Submission #444264

# Submission time Handle Problem Language Result Execution time Memory
444264 2021-07-13T13:01:35 Z peijar Comparing Plants (IOI20_plants) C++17
32 / 100
 1118 ms 49016 KB 
#include "plants.h"
#include <bits/stdc++.h>
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 + 1;
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, int want) {
  for (int p = MAXP - 1; p >= 0; --p) {
    int y = rgtEdge[x][p];
    if (order[y] < order[want])
      continue;
    int dis = (y - x + nbPlantes) % nbPlantes;
    if (dis <= d)
      d -= dis, x = y;
  }
  return x;
}

int goLeft(int x, int d, int want) {
  for (int p = MAXP - 1; p >= 0; --p) {
    int y = lftEdge[x][p];
    if (order[y] < order[want])
      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, y), x2 = goLeft(x, d2, y);
  // cout << d1 << ' ' << x1 << endl;
  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;
}

Subtask #1
5.0 / 5.0

# 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 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 89 ms 3032 KB Output is correct
7 Correct 136 ms 7588 KB Output is correct
8 Correct 434 ms 47796 KB Output is correct
9 Correct 468 ms 47784 KB Output is correct
10 Correct 499 ms 47780 KB Output is correct
11 Correct 526 ms 47876 KB Output is correct
12 Correct 524 ms 47832 KB Output is correct
13 Correct 532 ms 47784 KB Output is correct
14 Correct 600 ms 47788 KB Output is correct

Subtask #2
14.0 / 14.0

# 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 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 134 ms 4012 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 132 ms 4008 KB Output is correct
11 Correct 105 ms 3872 KB Output is correct
12 Correct 129 ms 4136 KB Output is correct
13 Correct 136 ms 4044 KB Output is correct

Subtask #3
13.0 / 13.0

# 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 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 588 KB Output is correct
7 Correct 134 ms 4012 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 132 ms 4008 KB Output is correct
11 Correct 105 ms 3872 KB Output is correct
12 Correct 129 ms 4136 KB Output is correct
13 Correct 136 ms 4044 KB Output is correct
14 Correct 183 ms 7536 KB Output is correct
15 Correct 1118 ms 47952 KB Output is correct
16 Correct 182 ms 7568 KB Output is correct
17 Correct 1067 ms 47864 KB Output is correct
18 Correct 668 ms 47820 KB Output is correct
19 Correct 750 ms 47956 KB Output is correct
20 Correct 1073 ms 47904 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 107 ms 3492 KB Output is correct
4 Correct 679 ms 49016 KB Output is correct
5 Correct 698 ms 47972 KB Output is correct
6 Incorrect 849 ms 47784 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 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 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 22 ms 928 KB Output is correct
8 Incorrect 23 ms 928 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 519 ms 47844 KB Output is correct
7 Correct 746 ms 47844 KB Output is correct
8 Incorrect 777 ms 47916 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 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 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 89 ms 3032 KB Output is correct
7 Correct 136 ms 7588 KB Output is correct
8 Correct 434 ms 47796 KB Output is correct
9 Correct 468 ms 47784 KB Output is correct
10 Correct 499 ms 47780 KB Output is correct
11 Correct 526 ms 47876 KB Output is correct
12 Correct 524 ms 47832 KB Output is correct
13 Correct 532 ms 47784 KB Output is correct
14 Correct 600 ms 47788 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 5 ms 588 KB Output is correct
21 Correct 134 ms 4012 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 5 ms 588 KB Output is correct
24 Correct 132 ms 4008 KB Output is correct
25 Correct 105 ms 3872 KB Output is correct
26 Correct 129 ms 4136 KB Output is correct
27 Correct 136 ms 4044 KB Output is correct
28 Correct 183 ms 7536 KB Output is correct
29 Correct 1118 ms 47952 KB Output is correct
30 Correct 182 ms 7568 KB Output is correct
31 Correct 1067 ms 47864 KB Output is correct
32 Correct 668 ms 47820 KB Output is correct
33 Correct 750 ms 47956 KB Output is correct
34 Correct 1073 ms 47904 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 107 ms 3492 KB Output is correct
38 Correct 679 ms 49016 KB Output is correct
39 Correct 698 ms 47972 KB Output is correct
40 Incorrect 849 ms 47784 KB Output isn't correct
41 Halted 0 ms 0 KB -