oj.uz

Submission #856309

# Submission time Handle Problem Language Result Execution time Memory
856309 2023-10-03T05:11:58 Z NeroZein Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 26884 KB 
#include "elephants.h"
#include "bits/stdc++.h"
 
using namespace std; 
 
const int B = 300; 
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; 
set<int> min_changed_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(); 
  min_changed_val.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); 
  }
  min_changed_val.insert(to_val[i]);
  to_val[i] = v; 
  min_changed_val.insert(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) {
      int above = INF;
      auto it2 = min_changed_val.lower_bound(c);
      if (it2 != min_changed_val.end()) {
        above = *it2; 
        assert(above <= d); 
      }
      for (int b = LOG - 1; b >= 0; --b) {
        if (!is_changed[nx[b][ind]] && nx[b][ind] < n && to_val[nx[b][ind]] < above) {
          c = to_val[nx[b][ind]], ind = nx[b][ind], ans += 1 << b;
        } 
      }
      ans++;
      x = max(c + l, above - 1);
    } 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 18780 KB Output is correct
3 Correct 2 ms 18860 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18860 KB Output is correct
4 Correct 2 ms 18776 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18860 KB Output is correct
4 Correct 2 ms 18776 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 495 ms 22400 KB Output is correct
8 Correct 633 ms 23076 KB Output is correct
9 Execution timed out 9038 ms 26884 KB Time limit exceeded
10 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 18780 KB Output is correct
3 Correct 2 ms 18860 KB Output is correct
4 Correct 2 ms 18776 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 495 ms 22400 KB Output is correct
8 Correct 633 ms 23076 KB Output is correct
9 Execution timed out 9038 ms 26884 KB Time limit exceeded
10 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 18780 KB Output is correct
3 Correct 2 ms 18860 KB Output is correct
4 Correct 2 ms 18776 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 495 ms 22400 KB Output is correct
8 Correct 633 ms 23076 KB Output is correct
9 Execution timed out 9038 ms 26884 KB Time limit exceeded
10 Halted 0 ms 0 KB -