oj.uz

답안 #856311

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
856311 2023-10-03T05:12:59 Z NeroZein 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
26 / 100
 9000 ms 27208 KB 
#include "elephants.h"
#include "bits/stdc++.h"
 
using namespace std; 
 
const int B = 150; 
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 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

# 결과 실행 시간 메모리 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 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 733 ms 22384 KB Output is correct
8 Correct 1028 ms 23220 KB Output is correct
9 Correct 6238 ms 27208 KB Output is correct
10 Correct 3433 ms 27196 KB Output is correct
11 Correct 3431 ms 27124 KB Output is correct
12 Execution timed out 9025 ms 27028 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 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 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 733 ms 22384 KB Output is correct
8 Correct 1028 ms 23220 KB Output is correct
9 Correct 6238 ms 27208 KB Output is correct
10 Correct 3433 ms 27196 KB Output is correct
11 Correct 3431 ms 27124 KB Output is correct
12 Execution timed out 9025 ms 27028 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 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 733 ms 22384 KB Output is correct
8 Correct 1028 ms 23220 KB Output is correct
9 Correct 6238 ms 27208 KB Output is correct
10 Correct 3433 ms 27196 KB Output is correct
11 Correct 3431 ms 27124 KB Output is correct
12 Execution timed out 9025 ms 27028 KB Time limit exceeded
13 Halted 0 ms 0 KB -