Submission #781714

#	Time	Username	Problem	Language	Result	Execution time	Memory
781714		I_Love_EliskaM_	Dancing Elephants (IOI11_elephants)	C++14	50 / 100	9023 ms	2252 KiB

elephants

#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(),x.end()
mt19937 rng(998244353);

const int N=50005;
int pos[N],ind[N],a[N];

int n,l;
void init(int _n, int _l, int x[]) {
  n=_n; l=_l; if (n>50000) exit(0);
  forn(i,n) a[i]=x[i];
  forn(i,n) pos[i]=ind[i]=i;
}
int update(int i, int x) {
  i=pos[i];
  if (x>a[i]) {
    while (i<n-1 && a[i+1]<x) {
      swap(ind[i],ind[i+1]);
      pos[ind[i]]=i;
      swap(a[i],a[i+1]);
      ++i;
    }
    a[i]=x;
    pos[ind[i]]=i;
  } else {
    while (i && a[i-1]>x) {
      swap(ind[i],ind[i-1]);
      pos[ind[i]]=i;
      swap(a[i],a[i-1]);
      --i;
    }
    a[i]=x;
    pos[ind[i]]=i;
  }
  
  int ans=0;
  int r=-1;
  forn(i,n) {
    if (a[i]>r) {
      r=a[i]+l;
      ++ans;
    }
  }
  return ans;
}

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