oj.uz

Submission #856310

# Submission time Handle Problem Language Result Execution time Memory
856310 2023-10-03T05:12:25 Z NeroZein Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 27648 KB 
#include "elephants.h"
#include "bits/stdc++.h"
 
using namespace std; 
 
const int B = 250; 
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 3 ms 18780 KB Output is correct
3 Correct 2 ms 18780 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 3 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 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 3 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 536 ms 22516 KB Output is correct
8 Correct 721 ms 23188 KB Output is correct
9 Correct 8228 ms 27112 KB Output is correct
10 Correct 2164 ms 26960 KB Output is correct
11 Correct 2137 ms 27024 KB Output is correct
12 Execution timed out 9017 ms 27648 KB Time limit exceeded
13 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 3 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 536 ms 22516 KB Output is correct
8 Correct 721 ms 23188 KB Output is correct
9 Correct 8228 ms 27112 KB Output is correct
10 Correct 2164 ms 26960 KB Output is correct
11 Correct 2137 ms 27024 KB Output is correct
12 Execution timed out 9017 ms 27648 KB Time limit exceeded
13 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 3 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 536 ms 22516 KB Output is correct
8 Correct 721 ms 23188 KB Output is correct
9 Correct 8228 ms 27112 KB Output is correct
10 Correct 2164 ms 26960 KB Output is correct
11 Correct 2137 ms 27024 KB Output is correct
12 Execution timed out 9017 ms 27648 KB Time limit exceeded
13 Halted 0 ms 0 KB -