Submission #410620

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

elephants

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

using namespace std;

const int N = 150000 + 7;
const int B = 400;
int n, len, normal_ord[N], rad, mx, v[N];
vector<int> bucket[B];
int ind;

void init(int nn, int lenlen, int initial[]) {
  n = nn;
  len = lenlen;
  ind = 0;

  rad = sqrt(nn);
  mx = (n - 1) / rad;

  for (int i = 0; i < B; i++) {
    bucket[i].clear();
  }

  for (int i = 0; i < n; i++) {
    normal_ord[i] = initial[i];
  }
}


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

int update(int ii, int yy) {

  if (ind % rad == 0) {
    /// It's rebuild time
    vector<int> values;
    for (int i = 0; i < n; i++) {
      values.push_back(normal_ord[i]);
    }
    sort(values.begin(), values.end());
    for (int i = 0; i <= mx; i++) {
      bucket[i].clear();
    }
    for (int i = 0; i < n; i++) {
      bucket[i / rad].push_back(values[i]);
    }
  }

  ind++;

  {
    int value = normal_ord[ii];
    normal_ord[ii] = yy;
    bool found = 0;
    for (int i = 0; i <= mx; i++) {
      if (bucket[i].empty()) continue;
      if (bucket[i][0] <= value && value <= bucket[i].back()) {
        int pos = -1;
        for (int j = 0; j < (int) bucket[i].size(); j++) {
          if (bucket[i][j] == value) {
            pos = j;
            break;
          }
        }
        vector<int> new_bucket;
        for (int j = 0; j < (int) bucket[i].size(); j++) {
          if (j != pos) {
            new_bucket.push_back(bucket[i][j]);
          }
        }
        bucket[i] = new_bucket;
        assert(pos != -1);
        found = 1;
        break;
      }
    }
    assert(found);
    int where = mx;
    for (int i = 0; i <= mx; i++) {
      if (bucket[i].empty()) continue;
      if (bucket[i].back() >= yy) {
        where = i;
        break;
      }
    }
    bucket[where].push_back(yy);
    int j = (int) bucket[where].size() - 1;
    while (j - 1 >= 0 && bucket[where][j - 1] > bucket[where][j]) {
      swap(bucket[where][j - 1], bucket[where][j]);
      j--;
    }
  }
  {
    int sz = 0;
    for (int i = 0; i <= mx; i++) {
      for (int j = 1; j < (int) bucket[i].size(); j++) {
        assert(bucket[i][j - 1] <= bucket[i][j]);
      }
      for (auto &x : bucket[i]) {
        v[sz++] = x;
      }
    }
  }
  int cost = 0, l = 0;
  while (l < n) {
    cost++;
    int r = l;
    while (r + 1 < n && v[r + 1] - v[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