Submission #14776

#	Time	Username	Problem	Language	Result	Execution time	Memory
14776		minsu	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	6607 ms	22272 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define MAXE 150051
#define BLOCK 400

int n, bn, l, ele[MAXE], tmp[MAXE], cooltime;
int p[BLOCK][BLOCK*2], sz[BLOCK][BLOCK*2], la[BLOCK][BLOCK*2], pn[BLOCK], pl[BLOCK];

void calc(int b){
  for(int i=pn[b]-1; i>=0; i--){
    int nxt = lower_bound( p[b]+i+1, p[b]+pn[b], p[b][i] + l + 1 ) - p[b];
    if( nxt == pn[b] ) sz[b][i] = 1, la[b][i] = p[b][i] + l + 1;
    else sz[b][i] = sz[b][nxt] + 1, la[b][i] = la[b][nxt];
  }
}

void mkblock( int X[] ){
  for(int i=0; i<bn; i++) pn[i] = 0;
  for(int i=0; i<n; i++){
    int b = i / BLOCK;
    int& bs = pn[b];
    p[b][bs++] = X[i];
  } bn = ( n-1 ) / BLOCK + 1;
  for(int i=0; i<bn; i++)
    calc(i), pl[i] = p[i][pn[i]-1];
}

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

int update(int i, int y)
{
  if( ++cooltime == BLOCK ){
    cooltime = 0;
    bool xd = false, ya = false; int tn = 0, x;
    x = ele[i]; ele[i] = y;
    for(int i=0; i<bn; i++)
      for(int j=0; j<pn[i]; j++){
        if( !xd && p[i][j] == x ) { xd = true; continue; }
        if( !ya && p[i][j] > y ) { ya = true; tmp[tn++] = y; }
        tmp[tn++] = p[i][j];
      }
    if(!ya) tmp[tn++] = y;
    mkblock( tmp );   
  }else{
    int xb = lower_bound( pl, pl + bn, ele[i] ) - pl;
    int xp = lower_bound( p[xb], p[xb] + pn[xb], ele[i] ) - p[xb];
    pn[xb]--; for(int i=xp; i<pn[xb]; i++) p[xb][i] = p[xb][i+1];
    calc(xb); if(pn[xb]!=0) pl[xb] = p[xb][pn[xb]-1];

    ele[i] = y;
    int yb = lower_bound( pl, pl + bn, ele[i] ) - pl; if(yb == bn) yb--;
    int yp = lower_bound( p[yb], p[yb] + pn[yb], ele[i] ) - p[yb];
    for(int i=pn[yb]; i>yp; i--) p[yb][i] = p[yb][i-1]; pn[yb]++; p[yb][yp] = ele[i];
    calc(yb); pl[yb] = p[yb][pn[yb]-1];
  }

  int ret = 0, pos = -1;
  for(int i=0; i<bn; i++){
    int j = lower_bound( p[i], p[i] + pn[i], pos ) - p[i];
    if( j == pn[i] ) continue;
    ret += sz[i][j]; pos = la[i][j];
  }
  return ret;
}

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