Submission #856281

#	Time	Username	Problem	Language	Result	Execution time	Memory
856281		NeroZein	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	19 ms	22108 KiB

elephants

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

using namespace std; 

const int N = 150003; 
const int LOG = 18; 
const int INF = 1e9; 
const int B = 400; 

int n, l, qc; 
int nx[LOG][N]; 
bool is_changed[N];
map<int, int> to_val; 
multiset<pair<int, int>> se; 
vector<pair<int, int>> changed;

void rebuild() {
  qc = 0; 
  vector<pair<int, int>> a; 
  for (int i = 0; i < n; ++i) {
    a.emplace_back(to_val[i], i); 
    is_changed[i] = false; 
  }
  changed.clear(); 
  se.clear(); 
  sort(a.begin(), a.end());
  int r = n - 1;
  for (int i = n - 1; i >= 0; --i) {
    while (r - 1 >= i && a[r - 1].first - a[i].first > l) {
      r--;
    }
    nx[0][a[i].second] = r + 1; 
    se.emplace(a[i]); 
  }
  for (int j = 1; j < LOG; ++j) {
    for (int i = 0; i < n; ++i) {
      nx[j][i] = nx[j - 1][nx[j - 1][i]]; 
    }
  }
}

void edit(int i, int v) {
  if (is_changed[i]) {
    for (int j = 0; j < (int) changed.size(); ++j) {
      if (changed[j].second == i) {
        changed.erase(changed.begin() + j);
        break; 
      }
    }
  } else {
    se.erase(se.find({to_val[i], i}));
  }
  bool f = false; 
  for (int j = 0; j < (int) changed.size(); ++j) {
    if (changed[j].first > v) {
      changed.insert(changed.begin() + j, {v, i}); 
      f = true;
      break;
    }
  }
  if (!f) {
    changed.emplace_back(v, i); 
  }
  to_val[i] = v; 
  is_changed[i] = true; 
}

void init(int N_, int L, int X[]) {
  n = N_, l = L; 
  for (int i = 0; i < n; ++i) {
    to_val[i] = X[i]; 
  }
  rebuild(); 
}

int update(int i, int y) {
  edit(i, y); 
  qc++;
  if (qc == B) {
    rebuild(); 
  }
  int x = -1, ptr = 0, ans = 0;
  while (true) {
    pair<int, int> key = {x, INF};
    auto it = se.upper_bound(key);
    int c = INF, ind = n;
    if (it != se.end()) {
      c = it->first, ind = it->second;
    }
    int d = INF;
    if (ptr < (int) changed.size()) {
      d = changed[ptr].first;
    }
    if (ind == n && ptr == (int) changed.size()) {
      break; 
    }
    if (c < d) {
      for (int b = LOG - 1; i >= b; --i) {
        if (nx[b][ind] && nx[b][ind] < n && to_val[nx[b][ind]] < d) {
          c = to_val[nx[b][ind]], ind = nx[b][ind], ans += 1 << b;
        }
      }
      ans++;
      assert(ind < n); 
      assert(to_val[ind] == c); 
      x = c + l;
    } else {
      ans++;
      x = d + l; 
    }
    while (ptr < (int) changed.size() && changed[ptr].first <= x) {
      ptr++;
    }
  } 
  return ans;
}

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