oj.uz

Submission #444265

# Submission time Handle Problem Language Result Execution time Memory
444265 2021-07-13T13:04:32 Z peijar Comparing Plants (IOI20_plants) C++17
32 / 100
 1092 ms 52296 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 = 20;

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 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 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 93 ms 3040 KB Output is correct
7 Correct 147 ms 7844 KB Output is correct
8 Correct 463 ms 51008 KB Output is correct
9 Correct 488 ms 50984 KB Output is correct
10 Correct 519 ms 51088 KB Output is correct
11 Correct 544 ms 51048 KB Output is correct
12 Correct 545 ms 50868 KB Output is correct
13 Correct 547 ms 50904 KB Output is correct
14 Correct 617 ms 50968 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 1 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 140 ms 4108 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 136 ms 4048 KB Output is correct
11 Correct 109 ms 4040 KB Output is correct
12 Correct 135 ms 4216 KB Output is correct
13 Correct 137 ms 4132 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 1 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 140 ms 4108 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 136 ms 4048 KB Output is correct
11 Correct 109 ms 4040 KB Output is correct
12 Correct 135 ms 4216 KB Output is correct
13 Correct 137 ms 4132 KB Output is correct
14 Correct 193 ms 7852 KB Output is correct
15 Correct 1075 ms 51052 KB Output is correct
16 Correct 200 ms 7876 KB Output is correct
17 Correct 1092 ms 51036 KB Output is correct
18 Correct 709 ms 51008 KB Output is correct
19 Correct 760 ms 50988 KB Output is correct
20 Correct 1092 ms 51152 KB Output is correct

Subtask #4
0 / 17.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 112 ms 3552 KB Output is correct
4 Correct 680 ms 52296 KB Output is correct
5 Correct 721 ms 51164 KB Output is correct
6 Incorrect 887 ms 51012 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 356 KB Output is correct
7 Correct 23 ms 1004 KB Output is correct
8 Incorrect 25 ms 924 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 3 ms 460 KB Output is correct
6 Correct 535 ms 51040 KB Output is correct
7 Correct 767 ms 50916 KB Output is correct
8 Incorrect 769 ms 51000 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 93 ms 3040 KB Output is correct
7 Correct 147 ms 7844 KB Output is correct
8 Correct 463 ms 51008 KB Output is correct
9 Correct 488 ms 50984 KB Output is correct
10 Correct 519 ms 51088 KB Output is correct
11 Correct 544 ms 51048 KB Output is correct
12 Correct 545 ms 50868 KB Output is correct
13 Correct 547 ms 50904 KB Output is correct
14 Correct 617 ms 50968 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 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 140 ms 4108 KB Output is correct
22 Correct 3 ms 332 KB Output is correct
23 Correct 5 ms 588 KB Output is correct
24 Correct 136 ms 4048 KB Output is correct
25 Correct 109 ms 4040 KB Output is correct
26 Correct 135 ms 4216 KB Output is correct
27 Correct 137 ms 4132 KB Output is correct
28 Correct 193 ms 7852 KB Output is correct
29 Correct 1075 ms 51052 KB Output is correct
30 Correct 200 ms 7876 KB Output is correct
31 Correct 1092 ms 51036 KB Output is correct
32 Correct 709 ms 51008 KB Output is correct
33 Correct 760 ms 50988 KB Output is correct
34 Correct 1092 ms 51152 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 0 ms 204 KB Output is correct
37 Correct 112 ms 3552 KB Output is correct
38 Correct 680 ms 52296 KB Output is correct
39 Correct 721 ms 51164 KB Output is correct
40 Incorrect 887 ms 51012 KB Output isn't correct
41 Halted 0 ms 0 KB -