oj.uz

Submission #228233

# Submission time Handle Problem Language Result Execution time Memory
228233 2020-04-30T08:52:40 Z anonymous Dancing Elephants (IOI11_elephants) C++14
0 / 100
 5 ms 384 KB 
#include <iostream>
#define MAXN 150005
#define K 300
#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]);}
            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;}
    printf("Rebuild %d\n",Q);
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -