oj.uz

Submission #410634

# Submission time Handle Problem Language Result Execution time Memory
410634 2021-05-23T08:04:36 Z 600Mihnea Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 13372 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, v[N];
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);
        assert(pos != -1);
        found = 1;
        break;
      }
    }
    assert(found);
    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 sz = 0;
    for (int i = 0; i <= mx; i++) {
      for (int j = 1; j < (int) bucket[i].size(); j++) {
        assert(bucket[i][j - 1] <= bucket[i][j]);
      }
      for (auto &x : bucket[i]) {
        v[sz++] = x;
      }
    }
  }


    int cost2 = 0, x = -1;
    for (int i = 0; i <= mx; i++) {
      if (bucket[i].empty()) continue;
      if (bucket[i].back() <= x) continue;

   ///   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;
        }
      }
      assert(sol != -1);


      cost2 += cost[i][sol];
      x = mxg[i][sol];
    }
  return cost2;

}

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 7304 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 7304 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 5 ms 7392 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 7304 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 5 ms 7392 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 1555 ms 8684 KB Output is correct
8 Correct 2077 ms 9964 KB Output is correct
9 Correct 5020 ms 10528 KB Output is correct
10 Correct 5114 ms 10828 KB Output is correct
11 Correct 5051 ms 9988 KB Output is correct
12 Correct 5683 ms 10032 KB Output is correct
13 Correct 5148 ms 11364 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7304 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 5 ms 7392 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 1555 ms 8684 KB Output is correct
8 Correct 2077 ms 9964 KB Output is correct
9 Correct 5020 ms 10528 KB Output is correct
10 Correct 5114 ms 10828 KB Output is correct
11 Correct 5051 ms 9988 KB Output is correct
12 Correct 5683 ms 10032 KB Output is correct
13 Correct 5148 ms 11364 KB Output is correct
14 Correct 2908 ms 10680 KB Output is correct
15 Correct 3673 ms 10676 KB Output is correct
16 Correct 8021 ms 12092 KB Output is correct
17 Execution timed out 9096 ms 13372 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 5 ms 7304 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 6 ms 7372 KB Output is correct
5 Correct 5 ms 7392 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 1555 ms 8684 KB Output is correct
8 Correct 2077 ms 9964 KB Output is correct
9 Correct 5020 ms 10528 KB Output is correct
10 Correct 5114 ms 10828 KB Output is correct
11 Correct 5051 ms 9988 KB Output is correct
12 Correct 5683 ms 10032 KB Output is correct
13 Correct 5148 ms 11364 KB Output is correct
14 Correct 2908 ms 10680 KB Output is correct
15 Correct 3673 ms 10676 KB Output is correct
16 Correct 8021 ms 12092 KB Output is correct
17 Execution timed out 9096 ms 13372 KB Time limit exceeded
18 Halted 0 ms 0 KB -