Submission #220490

#	Time	Username	Problem	Language	Result	Execution time	Memory
220490		anonymous	Dancing Elephants (IOI11_elephants)	C++14	10 / 100	9076 ms	384 KiB

elephants

#include "elephants.h"
#include <iostream>
#include <set>
#include <utility>
#include <cassert>
#define MAXN 150005
#define K 400
using namespace std;

int N, L, Q, Pos[MAXN];
bool stray[MAXN];
multiset <pair <int,int> > E, G, S; //all elephants: pos = id and ghost: pos = id
int nxt[MAXN][20];

void makeJump() {
    for (int i=0; i<=N; i++) {
        auto it = E.upper_bound({Pos[i] + L,MAXN});
        if (it == E.end()) {
            nxt[i][0] = N;
        } else {
            nxt[i][0] = (*it).second;
        }
        //printf("%d %d\n",i,nxt[i][0]);
    }
    for (int i=1; i<20; i++) {
        for (int j=0; j<=N; j++) {
            nxt[j][i] = nxt[nxt[j][i-1]][i-1];
        }
    }
}

int Next(int p) {
    auto it = E.upper_bound({p + L,MAXN});
    if (it == E.end()) {
        return(N);
    } else {
        return((*it).second);
    }
}

void init(int n, int l, int x[])
{
  N= n, L = l;
  for (int i=0; i<n; i++) {
    Pos[i] = x[i];
    E.insert({x[i], i});
  }
  E.insert({2e9 + 5, N}); //dummy
  Pos[N] = 2e9 + 5;
  makeJump();
}

int update(int i, int y)
{
  Q+=1;
  if (stray[i]) {
     S.erase(S.find({Pos[i], i}));
  } else {
     G.insert({Pos[i], i}); //old pos as considered in jump
     stray[i] = true;
  }
  E.erase(E.find({Pos[i], i}));
  E.insert({y, i});
  S.insert({y, i});
  Pos[i] = y;
  if (Q%K == 0) {
    G.clear();
    S.clear();
    for (int i=0; i<N; i++) {
        stray[i] = 0;
    }
    makeJump();
  }
  int at = (*E.begin()).second, Ans = 0;
  while (at != N) {
       if (stray[at]) {
           Ans+=1;
           at = Next(Pos[at]);
       } else {
           if (G.upper_bound({Pos[at],MAXN}) == G.end() && S.upper_bound({Pos[at],MAXN}) == S.end()) {
                for (int i = 19; i >= 0; i--) {
                    if (nxt[at][i] != N) {
                        at = nxt[at][i];
                        Ans += (1<<i);
                    }
                }
                Ans+=1;
                //Jump 1 more
                assert(nxt[at][0] == N && at != N);
                break;
           } else  {
                int CritPos = 0;
                if (S.upper_bound({Pos[at],MAXN}) == S.end() || *G.upper_bound({Pos[at],MAXN}) < *S.upper_bound({Pos[at],MAXN})) {
                    CritPos = (*G.upper_bound({Pos[at],MAXN})).first;
                } else {
                    CritPos = (*S.upper_bound({Pos[at],MAXN})).first;
                }
                for (int i = 19; i >= 0; i--) {
                    if (Pos[nxt[at][i]] < CritPos) {
                        at = nxt[at][i];
                        Ans += (1<<i);
                    }
                }
                Ans+=1;
                at = Next(Pos[at]);
           }
       }
  }
  return(Ans);
}

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