oj.uz

Submission #444284

# Submission time Handle Problem Language Result Execution time Memory
444284 2021-07-13T13:35:36 Z peijar Comparing Plants (IOI20_plants) C++17
58 / 100
 1356 ms 85924 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;
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.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 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 95 ms 4056 KB Output is correct
7 Correct 171 ms 13212 KB Output is correct
8 Correct 533 ms 85204 KB Output is correct
9 Correct 573 ms 85192 KB Output is correct
10 Correct 608 ms 85276 KB Output is correct
11 Correct 637 ms 85176 KB Output is correct
12 Correct 637 ms 85160 KB Output is correct
13 Correct 634 ms 85136 KB Output is correct
14 Correct 770 ms 85184 KB Output is correct

Subtask #2
14.0 / 14.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 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 116 ms 6736 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 5 ms 716 KB Output is correct
10 Correct 119 ms 6812 KB Output is correct
11 Correct 152 ms 6796 KB Output is correct
12 Correct 136 ms 6936 KB Output is correct
13 Correct 114 ms 6812 KB Output is correct

Subtask #3
13.0 / 13.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 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 116 ms 6736 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 5 ms 716 KB Output is correct
10 Correct 119 ms 6812 KB Output is correct
11 Correct 152 ms 6796 KB Output is correct
12 Correct 136 ms 6936 KB Output is correct
13 Correct 114 ms 6812 KB Output is correct
14 Correct 222 ms 13288 KB Output is correct
15 Correct 1304 ms 85924 KB Output is correct
16 Correct 215 ms 12868 KB Output is correct
17 Correct 1323 ms 84132 KB Output is correct
18 Correct 812 ms 84208 KB Output is correct
19 Correct 918 ms 84148 KB Output is correct
20 Correct 1356 ms 84056 KB Output is correct

Subtask #4
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 115 ms 5572 KB Output is correct
4 Correct 814 ms 85416 KB Output is correct
5 Correct 866 ms 84212 KB Output is correct
6 Correct 1055 ms 84112 KB Output is correct
7 Correct 1175 ms 84260 KB Output is correct
8 Incorrect 1349 ms 84092 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 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 24 ms 1308 KB Output is correct
8 Correct 23 ms 1316 KB Output is correct
9 Correct 23 ms 1336 KB Output is correct
10 Correct 23 ms 1316 KB Output is correct
11 Correct 24 ms 1332 KB Output is correct
12 Correct 25 ms 1320 KB Output is correct
13 Correct 27 ms 1316 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 1 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 3 ms 716 KB Output is correct
6 Correct 618 ms 84488 KB Output is correct
7 Correct 896 ms 84788 KB Output is correct
8 Correct 944 ms 85100 KB Output is correct
9 Correct 1249 ms 85048 KB Output is correct
10 Correct 610 ms 84540 KB Output is correct
11 Correct 882 ms 85028 KB Output is correct
12 Correct 639 ms 85804 KB Output is correct
13 Correct 683 ms 84820 KB Output is correct
14 Correct 846 ms 84608 KB Output is correct
15 Correct 1050 ms 84804 KB Output is correct
16 Correct 680 ms 84404 KB Output is correct
17 Correct 622 ms 84716 KB Output is correct

Subtask #7
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 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 95 ms 4056 KB Output is correct
7 Correct 171 ms 13212 KB Output is correct
8 Correct 533 ms 85204 KB Output is correct
9 Correct 573 ms 85192 KB Output is correct
10 Correct 608 ms 85276 KB Output is correct
11 Correct 637 ms 85176 KB Output is correct
12 Correct 637 ms 85160 KB Output is correct
13 Correct 634 ms 85136 KB Output is correct
14 Correct 770 ms 85184 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 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 116 ms 6736 KB Output is correct
22 Correct 3 ms 460 KB Output is correct
23 Correct 5 ms 716 KB Output is correct
24 Correct 119 ms 6812 KB Output is correct
25 Correct 152 ms 6796 KB Output is correct
26 Correct 136 ms 6936 KB Output is correct
27 Correct 114 ms 6812 KB Output is correct
28 Correct 222 ms 13288 KB Output is correct
29 Correct 1304 ms 85924 KB Output is correct
30 Correct 215 ms 12868 KB Output is correct
31 Correct 1323 ms 84132 KB Output is correct
32 Correct 812 ms 84208 KB Output is correct
33 Correct 918 ms 84148 KB Output is correct
34 Correct 1356 ms 84056 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 300 KB Output is correct
37 Correct 115 ms 5572 KB Output is correct
38 Correct 814 ms 85416 KB Output is correct
39 Correct 866 ms 84212 KB Output is correct
40 Correct 1055 ms 84112 KB Output is correct
41 Correct 1175 ms 84260 KB Output is correct
42 Incorrect 1349 ms 84092 KB Output isn't correct
43 Halted 0 ms 0 KB -