Submission #444284

#	Time	Username	Problem	Language	Result	Execution time	Memory
444284		peijar	Comparing Plants (IOI20_plants)	C++17	58 / 100	1356 ms	85924 KiB

plants

#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 = 20;
const int INF = 1e9;

int k;
int lftEdge[MAXN][MAXP], rgtEdge[MAXN][MAXP];
int deltaLft[MAXN][MAXP], deltaRight[MAXN][MAXP];
int nbPlusGrands[MAXN];
vector<int> order;
int nbPlantes;

struct Seg {
  int nbValeurs;
  vector<int> order;
  vector<int> valeurs;
  vector<int> iDeb, iFin, lazy, minVal;

  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) {
  return min({abs(x - y), abs(x + nbPlantes - y), abs(y + nbPlantes - x)});
}

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) {
    // cout << i << ' ';
    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;
    deltaLft[i][0] = (i - lftEdge[i][0] + nbPlantes) % nbPlantes;

    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;
    deltaRight[i][0] = (rgtEdge[i][0] - i + nbPlantes) % nbPlantes;
    seg.upd(i, order[i]);
  }
  // cout << endl;

  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];
      deltaLft[i][p + 1] = deltaLft[i][p] + deltaLft[lftEdge[i][p]][p];
      deltaRight[i][p + 1] = deltaRight[i][p] + deltaRight[rgtEdge[i][p]][p];
    }
  // for (int i = 0; i < nbPlantes; ++i)
  // cout << lftEdge[i][0] << ' ' << rgtEdge[i][0] << endl;
}

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;
    if (deltaRight[x][p] <= d) {
      d -= deltaRight[x][p], x = y;
      // cout << y << ' ';
    }
  }
  // cout << endl;
  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;
    if (deltaLft[x][p] <= d) {
      // cout << deltaLft[x][p] << ' ' << x << ' ' << p << endl;
      d -= deltaLft[x][p], 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;
  // cout << d2 << ' ' << x2 << endl;
  if (disCircle(x1, y) < k and order[x1] >= order[y])
    return true;
  if (disCircle(x2, y) < 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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 0 / 25