Submission #410635

#	Time	Username	Problem	Language	Result	Execution time	Memory
410635		600Mihnea	Dancing Elephants (IOI11_elephants)	C++17	100 / 100	8664 ms	21036 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;
vector<int> bucket[B];
vector<int> cost[N];
vector<int> mxg[N];
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 rebuild_bucket(int id) {
  cost[id].clear();
  mxg[id].clear();
  int sz = (int) bucket[id].size();
  cost[id].resize(sz, -1);
  mxg[id].resize(sz, -1);

  int piv = sz - 1;

  for (int j = sz - 1; j >= 0; j--) {
    while (bucket[id][piv] - bucket[id][j] > len) {
      piv--;
    }
    if (piv == sz - 1) {
      cost[id][j] = 1;
      mxg[id][j] = bucket[id][j] + len;
    } else {
      cost[id][j] = 1 + cost[id][piv + 1];
      mxg[id][j] = mxg[id][piv + 1];
    }
    /// cost[j] = ?
    /// mx[j] = ?
  }
}


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]);
    }
    for (int i = 0; i <= mx; i++) {
      rebuild_bucket(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;
        rebuild_bucket(i);
        found = 1;
        break;
      }
    }
    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--;
    }
    rebuild_bucket(where);
  }
  int ans = 0, x = -1;
  for (int i = 0; i <= mx; i++) {
    if (bucket[i].empty()) continue;
    if (bucket[i].back() <= x) continue;
    int l = 0, r = (int) bucket[i].size() - 1, sol = -1;
    while (l <= r) {
      int m = (l + r) / 2;
      if (bucket[i][m] > x) {
        sol = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    ans += cost[i][sol];
    x = mxg[i][sol];
  }
  return ans;
}

Compilation message (stderr)

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:90:10: warning: variable 'found' set but not used [-Wunused-but-set-variable]
   90 |     bool found = 0;
      |          ^~~~~

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