Submission #726076

#	Time	Username	Problem	Language	Result	Execution time	Memory
726076		Alex_tz307	Teams (IOI15_teams)	C++17	Compilation error	0 ms	0 KiB

teams

#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

const int kN = 1e5 + 5e4;
const int bucketSize = 150;
const int kBuckets = 100;
int n, len, a[kN], bucket[kN], indexInBucket[kN];
int updates, 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 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 reach = -1;

  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    if (!buckets[i].isEmpty()) {
      int index = buckets[i].upperBound(reach);

      if (index != buckets[i].getSize()) {
        res += buckets[i].jumps(index);
        reach = buckets[i].furthest(index);
      }
    }
  }

  return res;
}

int update(int index, int x) {
  buckets[bucket[index]].rem(indexInBucket[index]);

  a[index] = x;

  int lastBucket = 0, newBucket = -1;

  for (int i = 0; i <= (n - 1) / bucketSize; ++i) {
    if (!buckets[i].isEmpty()) {
      lastBucket = i;

      if (newBucket == -1 && x <= buckets[i].last()) {
        newBucket = i;
      }
    }
  }

  if (newBucket == -1) {
    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;
}
*/

Compilation message (stderr)

teams.cpp:2:10: fatal error: elephants.h: No such file or directory
    2 | #include "elephants.h"
      |          ^~~~~~~~~~~~~
compilation terminated.