oj.uz

Submission #365356

# Submission time Handle Problem Language Result Execution time Memory
365356 2021-02-11T14:04:37 Z WLZ Dancing Elephants (IOI11_elephants) C++14
100 / 100
 5011 ms 14220 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

int n, l, k;
vector<int> x;
vector< vector<int> > buckets, cnt, last;

void rebuild(int i) {
  cnt[i].resize((int) buckets[i].size());
  last[i].resize((int) buckets[i].size());  
  int ptr = (int) buckets[i].size();
  for (int j = (int) buckets[i].size() - 1; j >= 0; j--) {
    while (ptr > j && buckets[i][ptr - 1] > buckets[i][j] + l) ptr--;
    if (buckets[i].back() - l <= buckets[i][j]) cnt[i][j] = 1, last[i][j] = buckets[i][j] + l;
    else cnt[i][j] = cnt[i][ptr] + 1, last[i][j] = last[i][ptr];
  }
}

void init(int N, int L, int X[]) {
  n = N, l = L, k = sqrt(n);
  for (int i = 0; i < n; i++) x.push_back(X[i]);
  buckets.push_back({});
  for (int i = 0; i < n; i++) {
    if ((int) buckets.back().size() == k) buckets.push_back({});
    buckets.back().push_back(x[i]);
  }
  cnt.resize((int) buckets.size()); last.resize((int) buckets.size());
  for (int i = 0; i < (int) buckets.size(); i++) rebuild(i);
}

int calc() {
  int prev = -1, ans = 0;
  for (int i = 0; i < (int) buckets.size(); i++) {
    auto it = upper_bound(buckets[i].begin(), buckets[i].end(), prev);
    if (it == buckets[i].end()) continue;
    int j = it - buckets[i].begin();
    ans += cnt[i][j];
    prev = last[i][j];
  }
  return ans;
}

int cur = 0;

void rebuild() {
  vector<int> tmp;
  for (int i = 0; i < (int) buckets.size(); i++) {
    for (int j = 0; j < (int) buckets[i].size(); j++) {
      tmp.push_back(buckets[i][j]);
    }
    buckets[i].clear();
  }
  int idx = 0;
  for (int i = 0; i < (int) tmp.size(); i++) {
    if (buckets[idx].size() == k) idx++;
    buckets[idx].push_back(tmp[i]);
  }
  for (int i = 0; i < (int) buckets.size(); i++) rebuild(i);
}

int update(int i, int y) {
  if (++cur == (n + k - 1) / k) {
    rebuild();
    cur = 0;
  }
  int idx = 0;
  while (buckets[idx].back() < x[i]) idx++;
  for (auto it = buckets[idx].begin(); ; it++) {
    if (*it == x[i]) {
      buckets[idx].erase(it);
      break;
    }
  }
  if (buckets[idx].empty()) rebuild();
  else rebuild(idx);
  x[i] = y;
  idx = 0;
  while (idx < (int) buckets.size() && buckets[idx].back() < x[i]) idx++;
  if (idx == (int) buckets.size()) idx--;
  bool added = false;
  for (auto it = buckets[idx].begin(); it != buckets[idx].end(); it++) {
    if (*it > x[i]) {
      buckets[idx].insert(it, x[i]);
      added = true;
      break;
    }
  }
  if (!added) buckets[idx].push_back(x[i]);
  rebuild(idx);
  return calc();
}

Compilation message

elephants.cpp: In function 'void rebuild()':
elephants.cpp:56:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     if (buckets[idx].size() == k) idx++;
      |         ~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 306 ms 2540 KB Output is correct
8 Correct 398 ms 2800 KB Output is correct
9 Correct 479 ms 4316 KB Output is correct
10 Correct 583 ms 3964 KB Output is correct
11 Correct 598 ms 3984 KB Output is correct
12 Correct 700 ms 4408 KB Output is correct
13 Correct 552 ms 3932 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 306 ms 2540 KB Output is correct
8 Correct 398 ms 2800 KB Output is correct
9 Correct 479 ms 4316 KB Output is correct
10 Correct 583 ms 3964 KB Output is correct
11 Correct 598 ms 3984 KB Output is correct
12 Correct 700 ms 4408 KB Output is correct
13 Correct 552 ms 3932 KB Output is correct
14 Correct 399 ms 4048 KB Output is correct
15 Correct 633 ms 3580 KB Output is correct
16 Correct 1075 ms 5296 KB Output is correct
17 Correct 1270 ms 6448 KB Output is correct
18 Correct 1338 ms 6420 KB Output is correct
19 Correct 2383 ms 5992 KB Output is correct
20 Correct 1245 ms 6416 KB Output is correct
21 Correct 1244 ms 6244 KB Output is correct
22 Correct 978 ms 5484 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 306 ms 2540 KB Output is correct
8 Correct 398 ms 2800 KB Output is correct
9 Correct 479 ms 4316 KB Output is correct
10 Correct 583 ms 3964 KB Output is correct
11 Correct 598 ms 3984 KB Output is correct
12 Correct 700 ms 4408 KB Output is correct
13 Correct 552 ms 3932 KB Output is correct
14 Correct 399 ms 4048 KB Output is correct
15 Correct 633 ms 3580 KB Output is correct
16 Correct 1075 ms 5296 KB Output is correct
17 Correct 1270 ms 6448 KB Output is correct
18 Correct 1338 ms 6420 KB Output is correct
19 Correct 2383 ms 5992 KB Output is correct
20 Correct 1245 ms 6416 KB Output is correct
21 Correct 1244 ms 6244 KB Output is correct
22 Correct 978 ms 5484 KB Output is correct
23 Correct 3660 ms 12736 KB Output is correct
24 Correct 3788 ms 12868 KB Output is correct
25 Correct 2876 ms 12424 KB Output is correct
26 Correct 4996 ms 12020 KB Output is correct
27 Correct 5011 ms 11968 KB Output is correct
28 Correct 598 ms 5228 KB Output is correct
29 Correct 552 ms 5228 KB Output is correct
30 Correct 578 ms 5356 KB Output is correct
31 Correct 555 ms 5484 KB Output is correct
32 Correct 3613 ms 11860 KB Output is correct
33 Correct 3187 ms 11092 KB Output is correct
34 Correct 3592 ms 11808 KB Output is correct
35 Correct 3402 ms 14220 KB Output is correct
36 Correct 1953 ms 11708 KB Output is correct
37 Correct 3516 ms 14032 KB Output is correct
38 Correct 3553 ms 10868 KB Output is correct
39 Correct 3539 ms 11980 KB Output is correct
40 Correct 3379 ms 11068 KB Output is correct
41 Correct 4243 ms 13188 KB Output is correct
42 Correct 4275 ms 13200 KB Output is correct