Submission #856305

#	Time	Username	Problem	Language	Result	Execution time	Memory
856305		NeroZein	Dancing Elephants (IOI11_elephants)	C++17	10 / 100	3 ms	18780 KiB

elephants

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

using namespace std; 

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.first << ", " << p.second << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
 cout << "["; 
 for (auto it = v.begin(); it != v.end();) {
   cout << *it;
    if (++it != v.end()) cout << ", ";
  }
 return cout << "]";
}

const int B = 2; 
const int LOG = 18; 
const int N = 150003; 
const int INF = 1e9 + 7; 

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) {
    is_changed[i] = false; 
    a.emplace_back(to_val[i], i); 
  }
  se.clear(); 
  changed.clear(); 
  sort(a.begin(), a.end());
  int r = n - 1;
  for (int i = n - 1; i >= 0; --i) {
    while (r > i && a[r].first - a[i].first > l) {
      r--;
    }
    nx[0][a[i].second] = (r + 1 == n ? n : a[r + 1].second); 
    se.emplace(a[i]); 
  }
  for (int j = 1; j < LOG; ++j) {
    for (int i = 0; i < n; ++i) {
      nx[j][i] = (nx[j - 1][i] == n ? n : 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 (c == INF && d == INF) {
      break; 
    }
    if (c < d) {
      for (int b = LOG - 1; b >= 0; --b) {
        if (!is_changed[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++;
      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: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3