Submission #410602

#	Time	Username	Problem	Language	Result	Execution time	Memory
410602		600Mihnea	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9056 ms	3040 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

const int N = 150000 + 7;
int n, x[N], len, normal_ord[N];

int ind;

void init(int nn, int lenlen, int initial[]) {
  n = nn;
  len = lenlen;
  for (int i = 0; i < n; i++) {
    x[i] = normal_ord[i] = initial[i];
  }
  return;
}


void print(int v[]) {
  cout << " ----> ";
  for (int i = 0; i < n; i++) {
    cout << v[i] << " ";
  }
  cout << "\n";
}

int update(int ii, int yy) {
  {
    int value = normal_ord[ii];
    normal_ord[ii] = yy;
    int l = 0, r = n - 1, sol = -1;
    while (l <= r) {
      int m = (l + r) / 2;
      if (x[m] == value) {
        sol = m;
        break;
      }
      if (x[m] < value) {
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    assert(sol != -1);
    ii = sol;
  }
  x[ii] = yy;
  bool bad_lft = (ii - 1 >= 0 && x[ii - 1] > x[ii]);
  bool bad_rgh = (ii + 1 < n && x[ii + 1] < x[ii]);
  assert(!(bad_lft && bad_rgh));
  if (bad_lft) {
    while (ii - 1 >= 0 && x[ii - 1] > x[ii]) {
      swap(x[ii - 1], x[ii]);
      ii--;
    }
  }
  if (bad_rgh) {
    while (ii + 1 < n && x[ii + 1] < x[ii]) {
      swap(x[ii + 1], x[ii]);
      ii++;
    }
  }
  int cost = 0, l = 0;
  while (l < n) {
    cost++;
    int r = l;
    while (r + 1 < n && x[r + 1] - x[l] <= len) {
      r++;
    }
    l = r + 1;
  }

  return cost;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3