Submission #542504

#	Time	Username	Problem	Language	Result	Execution time	Memory
542504		elira	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	9033 ms	1704 KiB

elephants

#include "elephants.h"

#define MAXN 500002

int n, l;
int elephants[MAXN];
int positions[MAXN];

void init(int N, int L, int X[])
{
  l = L;
  n = N;
  for (int i=0; i < n; i++) {
    elephants[i] = X[i];
    positions[i] = X[i];
  }
}

int update(int i, int y)
{
  int result = 0;
  int last_covered = -1;
  int current_pos = elephants[i];
  elephants[i] = y;
  bool type = y < current_pos;
  int carrying = -1;
  bool eating = false;
  for (int i = 0; i < n; i++) {
    if (type) {
      if (positions[i] > y ) {
        carrying = positions[i];
        positions[i] = y;
        y = 2000000000;
        if (carrying == current_pos) {
          carrying = -1;
        }
      } else if (carrying != -1) {
        if (positions[i] == current_pos) {
          positions[i] = carrying;
          carrying = -1;
        } else {
          carrying ^= positions[i];
          positions[i] ^= carrying;
          carrying ^= positions[i];
        }
      }
    }
    else {
      if (eating) {
        if (positions[i+1] >= y || i == n-1) {
          positions[i] = y;
          eating = false;
        } else {
          positions[i] = positions[i+1];
        }
      } else if (positions[i] == current_pos) {
        current_pos = -1;
        eating = true;
        i--;
        continue;
      }
    }

    if (last_covered < positions[i]) {
      result++;
      last_covered = positions[i] + l;
    }
  }
  return result;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3