oj.uz

Submission #410635

# Submission time Handle Problem Language Result Execution time Memory
410635 2021-05-23T08:06:14 Z 600Mihnea Dancing Elephants (IOI11_elephants) C++17
100 / 100
 8664 ms 21036 KB 
#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

const int N = 150000 + 7;
const int B = 400;
int n, len, normal_ord[N], rad, mx;
vector<int> bucket[B];
vector<int> cost[N];
vector<int> mxg[N];
int ind;

void init(int nn, int lenlen, int initial[]) {
  n = nn;
  len = lenlen;
  ind = 0;

  rad = sqrt(nn);
  mx = (n - 1) / rad;

  for (int i = 0; i < B; i++) {
    bucket[i].clear();
  }

  for (int i = 0; i < n; i++) {
    normal_ord[i] = initial[i];
  }
}

void rebuild_bucket(int id) {
  cost[id].clear();
  mxg[id].clear();
  int sz = (int) bucket[id].size();
  cost[id].resize(sz, -1);
  mxg[id].resize(sz, -1);

  int piv = sz - 1;

  for (int j = sz - 1; j >= 0; j--) {
    while (bucket[id][piv] - bucket[id][j] > len) {
      piv--;
    }
    if (piv == sz - 1) {
      cost[id][j] = 1;
      mxg[id][j] = bucket[id][j] + len;
    } else {
      cost[id][j] = 1 + cost[id][piv + 1];
      mxg[id][j] = mxg[id][piv + 1];
    }
    /// cost[j] = ?
    /// mx[j] = ?
  }
}


void print(int v[]) {
  cout << " ----> ";
  for (int i = 0; i < n; i++) {
    cout << v[i] << " ";
  }
  cout << "\n";
}

int update(int ii, int yy) {

  if (ind % rad == 0) {
    /// It's rebuild time
    vector<int> values;
    for (int i = 0; i < n; i++) {
      values.push_back(normal_ord[i]);
    }
    sort(values.begin(), values.end());
    for (int i = 0; i <= mx; i++) {
      bucket[i].clear();
    }
    for (int i = 0; i < n; i++) {
      bucket[i / rad].push_back(values[i]);
    }
    for (int i = 0; i <= mx; i++) {
      rebuild_bucket(i);
    }
  }

  ind++;

  {
    int value = normal_ord[ii];
    normal_ord[ii] = yy;
    bool found = 0;
    for (int i = 0; i <= mx; i++) {
      if (bucket[i].empty()) continue;
      if (bucket[i][0] <= value && value <= bucket[i].back()) {
        int pos = -1;
        for (int j = 0; j < (int) bucket[i].size(); j++) {
          if (bucket[i][j] == value) {
            pos = j;
            break;
          }
        }
        vector<int> new_bucket;
        for (int j = 0; j < (int) bucket[i].size(); j++) {
          if (j != pos) {
            new_bucket.push_back(bucket[i][j]);
          }
        }
        bucket[i] = new_bucket;
        rebuild_bucket(i);
        found = 1;
        break;
      }
    }
    int where = mx;
    for (int i = 0; i <= mx; i++) {
      if (bucket[i].empty()) continue;
      if (bucket[i].back() >= yy) {
        where = i;
        break;
      }
    }
    bucket[where].push_back(yy);
    int j = (int) bucket[where].size() - 1;
    while (j - 1 >= 0 && bucket[where][j - 1] > bucket[where][j]) {
      swap(bucket[where][j - 1], bucket[where][j]);
      j--;
    }
    rebuild_bucket(where);
  }
  int ans = 0, x = -1;
  for (int i = 0; i <= mx; i++) {
    if (bucket[i].empty()) continue;
    if (bucket[i].back() <= x) continue;
    int l = 0, r = (int) bucket[i].size() - 1, sol = -1;
    while (l <= r) {
      int m = (l + r) / 2;
      if (bucket[i][m] > x) {
        sol = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    ans += cost[i][sol];
    x = mxg[i][sol];
  }
  return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:90:10: warning: variable 'found' set but not used [-Wunused-but-set-variable]
   90 |     bool found = 0;
      |          ^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 7 ms 7348 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 423 ms 8584 KB Output is correct
8 Correct 539 ms 8892 KB Output is correct
9 Correct 798 ms 9536 KB Output is correct
10 Correct 954 ms 9520 KB Output is correct
11 Correct 941 ms 9548 KB Output is correct
12 Correct 1499 ms 9716 KB Output is correct
13 Correct 960 ms 9724 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 7 ms 7348 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 423 ms 8584 KB Output is correct
8 Correct 539 ms 8892 KB Output is correct
9 Correct 798 ms 9536 KB Output is correct
10 Correct 954 ms 9520 KB Output is correct
11 Correct 941 ms 9548 KB Output is correct
12 Correct 1499 ms 9716 KB Output is correct
13 Correct 960 ms 9724 KB Output is correct
14 Correct 727 ms 9184 KB Output is correct
15 Correct 856 ms 9004 KB Output is correct
16 Correct 2283 ms 9960 KB Output is correct
17 Correct 2510 ms 10920 KB Output is correct
18 Correct 2722 ms 13060 KB Output is correct
19 Correct 1782 ms 12956 KB Output is correct
20 Correct 2553 ms 13068 KB Output is correct
21 Correct 2596 ms 13068 KB Output is correct
22 Correct 1656 ms 12436 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 7 ms 7348 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 423 ms 8584 KB Output is correct
8 Correct 539 ms 8892 KB Output is correct
9 Correct 798 ms 9536 KB Output is correct
10 Correct 954 ms 9520 KB Output is correct
11 Correct 941 ms 9548 KB Output is correct
12 Correct 1499 ms 9716 KB Output is correct
13 Correct 960 ms 9724 KB Output is correct
14 Correct 727 ms 9184 KB Output is correct
15 Correct 856 ms 9004 KB Output is correct
16 Correct 2283 ms 9960 KB Output is correct
17 Correct 2510 ms 10920 KB Output is correct
18 Correct 2722 ms 13060 KB Output is correct
19 Correct 1782 ms 12956 KB Output is correct
20 Correct 2553 ms 13068 KB Output is correct
21 Correct 2596 ms 13068 KB Output is correct
22 Correct 1656 ms 12436 KB Output is correct
23 Correct 5031 ms 19040 KB Output is correct
24 Correct 5537 ms 19108 KB Output is correct
25 Correct 4356 ms 19144 KB Output is correct
26 Correct 5639 ms 19140 KB Output is correct
27 Correct 6570 ms 18848 KB Output is correct
28 Correct 1291 ms 12356 KB Output is correct
29 Correct 1249 ms 12256 KB Output is correct
30 Correct 1327 ms 12252 KB Output is correct
31 Correct 1252 ms 12368 KB Output is correct
32 Correct 5136 ms 18368 KB Output is correct
33 Correct 5106 ms 17888 KB Output is correct
34 Correct 5507 ms 18764 KB Output is correct
35 Correct 4578 ms 21036 KB Output is correct
36 Correct 2883 ms 18344 KB Output is correct
37 Correct 7890 ms 20084 KB Output is correct
38 Correct 5395 ms 18064 KB Output is correct
39 Correct 5781 ms 18600 KB Output is correct
40 Correct 5496 ms 17672 KB Output is correct
41 Correct 8349 ms 18780 KB Output is correct
42 Correct 8664 ms 18920 KB Output is correct