oj.uz

Submission #444296

# Submission time Handle Problem Language Result Execution time Memory
444296 2021-07-13T14:16:27 Z peijar Comparing Plants (IOI20_plants) C++17
100 / 100
 1215 ms 83544 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 1;
const int MAXP = 19;
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) {
    // cerr << 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;
    if (rgtEdge[i][0] == nbPlantes)
      deltaRight[i][0] = INF;
    if (lftEdge[i][0] == nbPlantes)
      deltaLft[i][0] = INF;
    seg.upd(i, order[i]);
  }

  // cerr << 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];
      if (deltaLft[i][p + 1] > INF)
        deltaLft[i][p + 1] = INF;
      if (deltaRight[i][p + 1] > INF)
        deltaRight[i][p + 1] = INF;
    }
  // for (int i = 0; i < nbPlantes; ++i)
  // cerr << 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;
    }
  }
  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) {
      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);
  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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 92 ms 4056 KB Output is correct
7 Correct 152 ms 12832 KB Output is correct
8 Correct 522 ms 81960 KB Output is correct
9 Correct 558 ms 82088 KB Output is correct
10 Correct 592 ms 82072 KB Output is correct
11 Correct 615 ms 82092 KB Output is correct
12 Correct 620 ms 82080 KB Output is correct
13 Correct 627 ms 81984 KB Output is correct
14 Correct 720 ms 82116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 121 ms 6684 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 5 ms 716 KB Output is correct
10 Correct 116 ms 6672 KB Output is correct
11 Correct 117 ms 6548 KB Output is correct
12 Correct 137 ms 6776 KB Output is correct
13 Correct 112 ms 6680 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 296 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 5 ms 716 KB Output is correct
7 Correct 121 ms 6684 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 5 ms 716 KB Output is correct
10 Correct 116 ms 6672 KB Output is correct
11 Correct 117 ms 6548 KB Output is correct
12 Correct 137 ms 6776 KB Output is correct
13 Correct 112 ms 6680 KB Output is correct
14 Correct 188 ms 12952 KB Output is correct
15 Correct 1215 ms 82884 KB Output is correct
16 Correct 191 ms 12960 KB Output is correct
17 Correct 1189 ms 82944 KB Output is correct
18 Correct 790 ms 82608 KB Output is correct
19 Correct 852 ms 82856 KB Output is correct
20 Correct 1175 ms 82980 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 118 ms 5592 KB Output is correct
4 Correct 811 ms 83236 KB Output is correct
5 Correct 864 ms 82344 KB Output is correct
6 Correct 1035 ms 82552 KB Output is correct
7 Correct 1143 ms 82584 KB Output is correct
8 Correct 1205 ms 82916 KB Output is correct
9 Correct 761 ms 82216 KB Output is correct
10 Correct 785 ms 82252 KB Output is correct
11 Correct 622 ms 82256 KB Output is correct
12 Correct 767 ms 82376 KB Output is correct
13 Correct 761 ms 82344 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 304 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 23 ms 1312 KB Output is correct
8 Correct 23 ms 1312 KB Output is correct
9 Correct 23 ms 1316 KB Output is correct
10 Correct 23 ms 1356 KB Output is correct
11 Correct 23 ms 1368 KB Output is correct
12 Correct 24 ms 1308 KB Output is correct
13 Correct 21 ms 1312 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 606 ms 81556 KB Output is correct
7 Correct 889 ms 81704 KB Output is correct
8 Correct 911 ms 81872 KB Output is correct
9 Correct 1189 ms 81944 KB Output is correct
10 Correct 628 ms 81420 KB Output is correct
11 Correct 892 ms 81960 KB Output is correct
12 Correct 649 ms 82736 KB Output is correct
13 Correct 677 ms 81608 KB Output is correct
14 Correct 844 ms 81660 KB Output is correct
15 Correct 1041 ms 81656 KB Output is correct
16 Correct 601 ms 81376 KB Output is correct
17 Correct 600 ms 81424 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 92 ms 4056 KB Output is correct
7 Correct 152 ms 12832 KB Output is correct
8 Correct 522 ms 81960 KB Output is correct
9 Correct 558 ms 82088 KB Output is correct
10 Correct 592 ms 82072 KB Output is correct
11 Correct 615 ms 82092 KB Output is correct
12 Correct 620 ms 82080 KB Output is correct
13 Correct 627 ms 81984 KB Output is correct
14 Correct 720 ms 82116 KB Output is correct
15 Correct 0 ms 296 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 5 ms 716 KB Output is correct
21 Correct 121 ms 6684 KB Output is correct
22 Correct 3 ms 460 KB Output is correct
23 Correct 5 ms 716 KB Output is correct
24 Correct 116 ms 6672 KB Output is correct
25 Correct 117 ms 6548 KB Output is correct
26 Correct 137 ms 6776 KB Output is correct
27 Correct 112 ms 6680 KB Output is correct
28 Correct 188 ms 12952 KB Output is correct
29 Correct 1215 ms 82884 KB Output is correct
30 Correct 191 ms 12960 KB Output is correct
31 Correct 1189 ms 82944 KB Output is correct
32 Correct 790 ms 82608 KB Output is correct
33 Correct 852 ms 82856 KB Output is correct
34 Correct 1175 ms 82980 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 300 KB Output is correct
37 Correct 118 ms 5592 KB Output is correct
38 Correct 811 ms 83236 KB Output is correct
39 Correct 864 ms 82344 KB Output is correct
40 Correct 1035 ms 82552 KB Output is correct
41 Correct 1143 ms 82584 KB Output is correct
42 Correct 1205 ms 82916 KB Output is correct
43 Correct 761 ms 82216 KB Output is correct
44 Correct 785 ms 82252 KB Output is correct
45 Correct 622 ms 82256 KB Output is correct
46 Correct 767 ms 82376 KB Output is correct
47 Correct 761 ms 82344 KB Output is correct
48 Correct 0 ms 332 KB Output is correct
49 Correct 0 ms 304 KB Output is correct
50 Correct 0 ms 332 KB Output is correct
51 Correct 1 ms 332 KB Output is correct
52 Correct 1 ms 332 KB Output is correct
53 Correct 3 ms 460 KB Output is correct
54 Correct 23 ms 1312 KB Output is correct
55 Correct 23 ms 1312 KB Output is correct
56 Correct 23 ms 1316 KB Output is correct
57 Correct 23 ms 1356 KB Output is correct
58 Correct 23 ms 1368 KB Output is correct
59 Correct 24 ms 1308 KB Output is correct
60 Correct 21 ms 1312 KB Output is correct
61 Correct 108 ms 5468 KB Output is correct
62 Correct 158 ms 12884 KB Output is correct
63 Correct 605 ms 82212 KB Output is correct
64 Correct 774 ms 82344 KB Output is correct
65 Correct 977 ms 82472 KB Output is correct
66 Correct 1100 ms 82728 KB Output is correct
67 Correct 1183 ms 82728 KB Output is correct
68 Correct 745 ms 82344 KB Output is correct
69 Correct 1056 ms 83024 KB Output is correct
70 Correct 788 ms 83544 KB Output is correct
71 Correct 835 ms 82344 KB Output is correct
72 Correct 1026 ms 82468 KB Output is correct
73 Correct 1142 ms 82732 KB Output is correct
74 Correct 636 ms 82048 KB Output is correct
75 Correct 733 ms 82216 KB Output is correct