Submission #777405

#	Time	Username	Problem	Language	Result	Execution time	Memory
777405		a_aguilo	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	50 / 100	9018 ms	2468 KiB

elephants

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

using namespace std;


const int maxN = 150000;
int n, l;
int positionsCameras[maxN];
int positions[maxN];
int posPerNumber[maxN];

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

int find(int rep){
  int hi = n-1;
  int lo = 0;
  while(lo <= hi){
    int mid = lo + (hi - lo)/2;
    if(positions[mid] == rep) return mid;
    if(positions[mid] < rep) lo = mid+1;
    else hi = mid-1;
  }
  return 0;
}

int update(int i, int y)
{
  int replace = posPerNumber[i];
  posPerNumber[i] = y;
  int pos = find(replace);
  positions[pos] = y;
  while(pos && positions[pos] < positions[pos-1]) {
    swap(positions[pos], positions[pos-1]);
    pos--;
  }
  while(pos < (n-1) && positions[pos] > positions[pos+1]) {
    swap(positions[pos], positions[pos+1]);
    pos++;
  }
  int numCameras = 0;
  int right = -1;
  for(int j = 0; j < n; ++j){
    if(right < positions[j]){
      numCameras++;
      right = positions[j] + l;
    }
  }
  return numCameras;
}

/*
int main(){
  int N, L, Q, i, y;
  cin >> N >> L;
  int X[N];
  for(int i = 0; i < N; ++i) cin >> X[i];
  init(N, L, X);
  cin >> Q;
  while(Q--){
    cin >> i >> y;
    cout << update(i, y) << endl;
  }
  return 0;
}
*/

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