oj.uz

Submission #444172

# Submission time Handle Problem Language Result Execution time Memory
444172 2021-07-13T08:53:49 Z peijar Comparing Plants (IOI20_plants) C++17
59 / 100
 1008 ms 32672 KB 
#include "plants.h"
#include <bits/stdc++.h>
#include <type_traits>
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;

int k;
int nbPlusGrands[MAXN], cntEq[MAXN][2];
vector<int> adj[MAXN];
int ordre[MAXN];
int nbDevant[MAXN];
bool reach[301][301];
vector<int> orderLarge, orderSmall;
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);
  }

  int queryMin(int iNoeud, int deb, int fin) {
    push(iNoeud);
    if (deb > iFin[iNoeud] or fin < iDeb[iNoeud])
      return 2 * INF;
    if (iDeb[iNoeud] >= deb and iFin[iNoeud] <= fin)
      return minVal[iNoeud];
    return min(queryMin(2 * iNoeud, deb, fin),
               queryMin(2 * iNoeud + 1, deb, fin));
  }

  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() {
    /*cout << "FINDING NEXT : " << endl;
    for (int i = 0; i < nbValeurs; ++i)
      cout << queryMin(1, i, i) << ' ';
    cout << endl;*/
    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;
}

void init(int _k, vector<int> r) {
  k = _k;
  nbPlantes = r.size();
  for (int iPlante = 0; iPlante < nbPlantes; ++iPlante) {
    nbPlusGrands[iPlante] = r[iPlante];
  }

  Seg segMax(r);
  for (int i = 0; i < nbPlantes; ++i)
    r[i] = k - 1 - r[i];
  Seg segMin(r);
  orderLarge.resize(nbPlantes);
  orderSmall.resize(nbPlantes);
  for (int i = 0; i < nbPlantes; ++i) {
    orderLarge[segMax.order[i]] = nbPlantes - 1 - i;
    orderSmall[segMin.order[i]] = i;
  }
  /*for (auto v : orderLarge)
    cout << v << ' ';
  cout << endl;
  for (auto v : orderSmall)
    cout << v << ' ';
  cout << endl;*/
}

int compare_plants(int x, int y) {
  if (x > y)
    return -compare_plants(y, x);
  if (orderSmall[x] > orderSmall[y])
    return 1;
  if (orderLarge[x] < orderLarge[y])
    return -1;
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 8 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 85 ms 8524 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 7 ms 5068 KB Output is correct
10 Correct 79 ms 8540 KB Output is correct
11 Correct 69 ms 8408 KB Output is correct
12 Correct 71 ms 8668 KB Output is correct
13 Correct 77 ms 8540 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 85 ms 8524 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 7 ms 5068 KB Output is correct
10 Correct 79 ms 8540 KB Output is correct
11 Correct 69 ms 8408 KB Output is correct
12 Correct 71 ms 8668 KB Output is correct
13 Correct 77 ms 8540 KB Output is correct
14 Correct 130 ms 10132 KB Output is correct
15 Correct 980 ms 31084 KB Output is correct
16 Correct 126 ms 10180 KB Output is correct
17 Correct 1004 ms 31172 KB Output is correct
18 Correct 610 ms 31016 KB Output is correct
19 Correct 594 ms 31116 KB Output is correct
20 Correct 954 ms 31288 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 64 ms 8016 KB Output is correct
4 Correct 474 ms 32596 KB Output is correct
5 Correct 578 ms 31136 KB Output is correct
6 Correct 772 ms 31048 KB Output is correct
7 Correct 901 ms 31284 KB Output is correct
8 Correct 1008 ms 31088 KB Output is correct
9 Correct 503 ms 31176 KB Output is correct
10 Correct 514 ms 31032 KB Output is correct
11 Correct 398 ms 31276 KB Output is correct
12 Correct 460 ms 31228 KB Output is correct
13 Correct 619 ms 31156 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Incorrect 3 ms 4940 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4980 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 6 ms 5068 KB Output is correct
6 Correct 569 ms 31224 KB Output is correct
7 Correct 755 ms 31064 KB Output is correct
8 Correct 884 ms 31112 KB Output is correct
9 Correct 976 ms 31016 KB Output is correct
10 Correct 502 ms 31128 KB Output is correct
11 Correct 716 ms 31000 KB Output is correct
12 Correct 464 ms 32672 KB Output is correct
13 Correct 558 ms 31400 KB Output is correct
14 Correct 745 ms 31140 KB Output is correct
15 Correct 903 ms 31128 KB Output is correct
16 Correct 467 ms 31196 KB Output is correct
17 Correct 538 ms 31148 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 8 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -