oj.uz

Submission #856301

# Submission time Handle Problem Language Result Execution time Memory
856301 2023-10-03T04:17:51 Z NeroZein Dancing Elephants (IOI11_elephants) C++17
10 / 100
 2 ms 18876 KB 
#include "elephants.h"
#include "bits/stdc++.h"

using namespace std; 

const int B = 400; 
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;
  //int steps = 0; 
  while (true) {
    //steps++;
    //assert(steps < 2 * n); 
    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) {
          assert(to_val[nx[b][ind]] > c);
          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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18876 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18876 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Incorrect 2 ms 18780 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18876 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Incorrect 2 ms 18780 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18876 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Incorrect 2 ms 18780 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18876 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Incorrect 2 ms 18780 KB Output isn't correct
5 Halted 0 ms 0 KB -