oj.uz

Submission #726115

# Submission time Handle Problem Language Result Execution time Memory
726115 2023-04-18T13:32:21 Z Alex_tz307 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7077 ms 8652 KB 
#include <bits/stdc++.h>
#include "elephants.h"
 
using namespace std;
 
const int kN = 1e5 + 5e4;
const int bucketSize = 750;
const int kBuckets = 200;
int n, len, a[kN], bucket[kN], indexInBucket[kN];
int updates, auxSize, auxIndices[kN];
 
class bucket_t {
  private:
    int N = 0, indices[2 * bucketSize];
    int req[2 * bucketSize], maxReach[2 * bucketSize];
 
  public:
    bool isEmpty() {
      return N == 0;
    }
 
    int getSize() {
      return N;
    }
 
    int last() {
      return a[indices[N - 1]];
    }
 
    void add(int index) {
      indices[N++] = index;
    }
 
    void addAll() {
      for (int i = 0; i < N; ++i) {
        auxIndices[auxSize++] = indices[i];
      }
      N = 0;
    }
 
    int cameras(int index) {
      return req[index];
    }
 
    int furthest(int index) {
      return maxReach[index];
    }
 
    void build() {
      int r = N - 1;
 
      for (int l = N - 1; l >= 0; --l) {
        while (a[indices[r]] - a[indices[l]] > len) {
          r -= 1;
        }
 
        if (r == N - 1) {
          req[l] = 1;
          maxReach[l] = a[indices[l]] + len;
        } else {
          req[l] = req[r + 1] + 1;
          maxReach[l] = maxReach[r + 1];
        }
      }
    }
 
    void rem(int pos) {
      for (int i = pos; i < N - 1; ++i) {
        indices[i] = indices[i + 1];
        indexInBucket[indices[i]] = i;
      }
 
      N -= 1;
 
      build();
    }
 
    void ins(int index) {
      int ptr = N - 1;
 
      while (ptr >= 0 && a[index] < a[indices[ptr]]) {
        ptr -= 1;
      }
 
      for (int i = N; i > ptr + 1; --i) {
        indices[i] = indices[i - 1];
        indexInBucket[indices[i]] = i;
      }
 
      indices[ptr + 1] = index;
      indexInBucket[index] = ptr + 1;
 
      N += 1;
 
      build();
    }
 
    int upperBound(int x) {
      int l = -1, r = N;
 
      while (r - l > 1) {
        int mid = (l + r) / 2;
 
        if (mid != -1 && (mid == N || x < a[indices[mid]])) {
          r = mid;
        } else {
          l = mid;
        }
      }
 
      return r;
    }
} buckets[kBuckets];
 
void init(int N, int L, int X[]) {
  n = N;
  len = L;
 
  for (int i = 0; i < n; ++i) {
    a[i] = X[i];
    bucket[i] = i / bucketSize;
    indexInBucket[i] = i % bucketSize;
    buckets[i / bucketSize].add(i);
  }
 
  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    buckets[i].build();
  }
}
 
void rebuild() {
  auxSize = 0;
 
  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    buckets[i].addAll();
  }
 
  for (int i = 0; i < n; ++i) {
    bucket[auxIndices[i]] = i / bucketSize;
    indexInBucket[auxIndices[i]] = i % bucketSize;
    buckets[i / bucketSize].add(auxIndices[i]);
  }
 
  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    buckets[i].build();
  }
}
 
int query() {
  int res = 0;
 
  int reach = -1;
 
  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    if (!buckets[i].isEmpty() && reach < buckets[i].last()) {
      int index = buckets[i].upperBound(reach);
      res += buckets[i].cameras(index);
      reach = buckets[i].furthest(index);
    }
  }
 
  return res;
}
 
int update(int index, int x) {
  buckets[bucket[index]].rem(indexInBucket[index]);
 
  a[index] = x;
  bucket[index] = -1;
 
  for (int i = 0; i <= (n - 1) / bucketSize && bucket[index] == -1; ++i) {
    if (!buckets[i].isEmpty() && x <= buckets[i].last()) {
      bucket[index] = i;
    }
  }
 
  if (bucket[index] == -1) {
    bucket[index] = (n - 1) / bucketSize;
  }
 
  buckets[bucket[index]].ins(index);
 
  updates += 1;
 
  if (updates == bucketSize) {
    rebuild();
    updates = 0;
  }
 
  return query();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 546 ms 2204 KB Output is correct
8 Correct 529 ms 2400 KB Output is correct
9 Correct 781 ms 3608 KB Output is correct
10 Correct 663 ms 3604 KB Output is correct
11 Correct 645 ms 3608 KB Output is correct
12 Correct 1094 ms 3608 KB Output is correct
13 Correct 634 ms 3604 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 546 ms 2204 KB Output is correct
8 Correct 529 ms 2400 KB Output is correct
9 Correct 781 ms 3608 KB Output is correct
10 Correct 663 ms 3604 KB Output is correct
11 Correct 645 ms 3608 KB Output is correct
12 Correct 1094 ms 3608 KB Output is correct
13 Correct 634 ms 3604 KB Output is correct
14 Correct 534 ms 2624 KB Output is correct
15 Correct 775 ms 2836 KB Output is correct
16 Correct 1847 ms 3836 KB Output is correct
17 Correct 1845 ms 4720 KB Output is correct
18 Correct 1929 ms 4596 KB Output is correct
19 Correct 1217 ms 4596 KB Output is correct
20 Correct 1818 ms 4600 KB Output is correct
21 Correct 1753 ms 4596 KB Output is correct
22 Correct 1002 ms 4596 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 546 ms 2204 KB Output is correct
8 Correct 529 ms 2400 KB Output is correct
9 Correct 781 ms 3608 KB Output is correct
10 Correct 663 ms 3604 KB Output is correct
11 Correct 645 ms 3608 KB Output is correct
12 Correct 1094 ms 3608 KB Output is correct
13 Correct 634 ms 3604 KB Output is correct
14 Correct 534 ms 2624 KB Output is correct
15 Correct 775 ms 2836 KB Output is correct
16 Correct 1847 ms 3836 KB Output is correct
17 Correct 1845 ms 4720 KB Output is correct
18 Correct 1929 ms 4596 KB Output is correct
19 Correct 1217 ms 4596 KB Output is correct
20 Correct 1818 ms 4600 KB Output is correct
21 Correct 1753 ms 4596 KB Output is correct
22 Correct 1002 ms 4596 KB Output is correct
23 Correct 4953 ms 8528 KB Output is correct
24 Correct 4897 ms 8528 KB Output is correct
25 Correct 4093 ms 8528 KB Output is correct
26 Correct 4207 ms 8532 KB Output is correct
27 Correct 4345 ms 8524 KB Output is correct
28 Correct 2129 ms 3136 KB Output is correct
29 Correct 2103 ms 3072 KB Output is correct
30 Correct 2146 ms 3148 KB Output is correct
31 Correct 2043 ms 3064 KB Output is correct
32 Correct 3787 ms 8652 KB Output is correct
33 Correct 2542 ms 8532 KB Output is correct
34 Correct 4025 ms 8528 KB Output is correct
35 Correct 2384 ms 8520 KB Output is correct
36 Correct 1175 ms 8532 KB Output is correct
37 Correct 5271 ms 8648 KB Output is correct
38 Correct 4417 ms 8532 KB Output is correct
39 Correct 4263 ms 8532 KB Output is correct
40 Correct 4396 ms 8532 KB Output is correct
41 Correct 7077 ms 8524 KB Output is correct
42 Correct 6578 ms 8528 KB Output is correct