Submission #228265

#	Time	Username	Problem	Language	Result	Execution time	Memory
228265		anonymous	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	4908 ms	13176 KiB

elephants

#include <iostream>
#define MAXN 150005
#define K 400
#include "elephants.h"
using namespace std;
int N, L, Q, B, Pos[MAXN], Bid[MAXN], Sort[MAXN]; //0 indexed

class Block {
public:
    int Sz, Id[2 * K + 5]; //ID sorted by Pos
    int Cost[2 * K + 5], Last[2 * K + 5];
    void Insert(int id) {
        Id[Sz] = id, Sz++;
        int pt = Sz-1;
        while (pt > 0) {
            if (Pos[Id[pt]] < Pos[Id[pt-1]]) {swap(Id[pt], Id[pt-1]);}
            else {break;}
            pt--;
        }
    }
    void Del(int id) {
        for (int i=0; i<Sz-1; i++) {
            if (Id[i] == id) {swap(Id[i], Id[i+1]);}
        }
        Sz-=1;
    }
    void slv() {
        int pt = Sz-1;
        for (int i=Sz-1; i>=0; i--) {
            while (pt > 0 && Pos[Id[pt-1]] > Pos[Id[i]] + L) {pt--;}
            if (Pos[Id[Sz-1]] <= Pos[Id[i]] + L) {
                Cost[i] = 1, Last[i]=Id[i];
            } else {
                Cost[i] = Cost[pt] + 1, Last[i]=Last[pt];
            }
        }
    }
    int ub(int x) {
        if (Sz == 0) {return(-1);}
        int lo = -1, hi = Sz;
        while (lo + 1 != hi) {
            int mid = (lo + hi) >> 1;
            if (Pos[Id[mid]] > x) {hi = mid;}
            else {lo = mid;}
        }
        if (hi == Sz) {return(-1);}
        return(hi);
    }
} Blk[MAXN/K + 5];

void build() {
    if (Q%K != 0) {return;}
    int ind = 0, bcur = -1;
    if (Q == 0) {
        for (int i=0; i<N; i++) {
            Sort[i] = i;
        } //already sorted
    } else {
        for (int i=0; i<B; i++) {
            for (int j=0; j < Blk[i].Sz; j++) {
                Sort[ind] = Blk[i].Id[j];
                ind++;
            }
            Blk[i].Sz = 0;
        }
    }
    for (int i=0; i<N; i++) {
        if (i % K == 0) {
            if (bcur >= 0) {Blk[bcur].slv();}
            bcur++;
        }
        Blk[bcur].Insert(Sort[i]);
        Bid[Sort[i]] = bcur;
    }
    Blk[bcur].slv();
    B= bcur+1;
}


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

int update(int id, int y)
{
  Q+=1;
  Blk[Bid[id]].Del(id);
  Blk[Bid[id]].slv();
  Pos[id] = y;
  for (int i=0; i<B; i++) {
    if ((Blk[i+1].Sz > 0 && Pos[Blk[i+1].Id[0]]>=y) || i == B-1) {
        Blk[i].Insert(id);
        Bid[id] = i;
        Blk[i].slv();
        break;
    }
  }
  build();
  int cost = 0, prev = -1<<30;
  for (int i=0; i<B; i++) {
      int New = Blk[i].ub(prev + L);
      if (New == -1) {continue;}
      else {
          prev = Pos[Blk[i].Last[New]];
          cost += Blk[i].Cost[New];
      }
  }
  return(cost);
}

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