oj.uz

Submission #410620

# Submission time Handle Problem Language Result Execution time Memory
410620 2021-05-23T07:24:25 Z 600Mihnea Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 3972 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];
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 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]);
    }
  }

  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;
        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--;
    }
  }
  {
    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 cost = 0, l = 0;
  while (l < n) {
    cost++;
    int r = l;
    while (r + 1 < n && v[r + 1] - v[l] <= len) {
      r++;
    }
    l = r + 1;
  }

  return cost;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3955 ms 1320 KB Output is correct
8 Correct 5495 ms 1628 KB Output is correct
9 Correct 6737 ms 2336 KB Output is correct
10 Correct 7013 ms 2396 KB Output is correct
11 Correct 6027 ms 3676 KB Output is correct
12 Execution timed out 9026 ms 3972 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3955 ms 1320 KB Output is correct
8 Correct 5495 ms 1628 KB Output is correct
9 Correct 6737 ms 2336 KB Output is correct
10 Correct 7013 ms 2396 KB Output is correct
11 Correct 6027 ms 3676 KB Output is correct
12 Execution timed out 9026 ms 3972 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3955 ms 1320 KB Output is correct
8 Correct 5495 ms 1628 KB Output is correct
9 Correct 6737 ms 2336 KB Output is correct
10 Correct 7013 ms 2396 KB Output is correct
11 Correct 6027 ms 3676 KB Output is correct
12 Execution timed out 9026 ms 3972 KB Time limit exceeded
13 Halted 0 ms 0 KB -