Submission #726054

# Submission time Handle Problem Language Result Execution time Memory
726054 2023-04-18T11:46:58 Z Alex_tz307 Dancing Elephants (IOI11_elephants) C++17
10 / 100
1 ms 340 KB
#include <bits/stdc++.h>
#include "elephants.h"
 
using namespace std;
 
const int kN = 1e5 + 5e4;
const int bucketSize = 2;
const int kBuckets = 1e5;
int n, len, a[kN], bucket[kN], indexInBucket[kN];
int updates;
int auxSize, auxIndices[kN];
 
class bucket_t {
  private:
    int N, indices[2 * bucketSize];
    int req[2 * bucketSize], maxReach[2 * bucketSize];
 
  public:
    void reset() {
      N = 0;
    }
 
    bool isEmpty() {
      return N == 0;
    }
 
    int getSize() {
      return N;
    }
 
    int first() {
      return a[indices[0]];
    }
 
    int last() {
      return a[indices[N - 1]];
    }
 
    void add(int index) {
      indices[N] = index;
      N += 1;
    }
 
    void addAll() {
      for (int i = 0; i < N; ++i) {
        auxIndices[auxSize] = indices[i];
        auxSize += 1;
      }
    }
 
    int jumps(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 - 1) / bucketSize; ++i) {
    buckets[i].reset();
  }
 
  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 - 1) / bucketSize; ++i) {
    buckets[i].reset();
  }
 
  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 value = -1;
 
  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    if (!buckets[i].isEmpty()) {
      int index = buckets[i].upperBound(value);
 
      if (index != buckets[i].getSize()) {
        res += buckets[i].jumps(index);
        value = buckets[i].furthest(index);
      }
    }
  }
 
  return res;
}
 
int update(int index, int x) {
  buckets[bucket[index]].rem(indexInBucket[index]);
 
  a[index] = x;
 
  int firstBucket = 0, lastBucket = 0, newBucket = -1;
 
  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    if (!buckets[i].isEmpty()) {
      if (firstBucket == -1) {
        firstBucket = i;
      }
 
      lastBucket = i;
 
      if (buckets[i].first() <= x && x <= buckets[i].last()) {
        newBucket = i;
      }
    }
  }
 
  if (newBucket == -1) {
    if (x < buckets[firstBucket].first()) {
      newBucket = firstBucket;
    } else {
      newBucket = lastBucket;
    }
  }
 
  bucket[index] = newBucket;
  buckets[newBucket].ins(index);
 
  updates += 1;
 
  if (updates == bucketSize) {
    rebuild();
    updates = 0;
  }
 
  return query();
}
 
/*
4 10 5
10
15
17
20
2 16 1
1 25 2
3 35 2
0 38 2
2 0 3
 
#define MAX_N 1000000
#define MAX_M 1000000
 
static int N,L,M;
static int X[MAX_N];
static int ii[MAX_M];
static int yy[MAX_M];
static int sol[MAX_M];
 
inline
void my_assert(int e) {if (!e) abort();}
 
void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&L,&M));
  for(i=0; i<N; i++)
    my_assert(1==scanf("%d",&X[i]));
  for(i=0; i<M; i++)
    my_assert(3==scanf("%d %d %d",&ii[i],&yy[i],&sol[i]));
}
 
int main()
{
  int i, ans;
 
  read_input();
  init(N,L,X);
  for(i=0; i<M; i++) {
    ans = update(ii[i],yy[i]);
    if(ans==sol[i])continue;
      printf("Incorrect.  In %d-th move, answered %d (%d expected).\n",
	     i+1, ans, sol[i]);
    return 0;
  }
  printf("Correct.\n");
  return 0;
}
*/
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -