Submission #671789

#	Time	Username	Problem	Language	Result	Execution time	Memory
671789		Hacv16	Dancing Elephants (IOI11_elephants)	C++17	0 / 100	1 ms	468 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int MAX = 1e3 + 15;

int n, L, x[MAX], block[MAX], T, dist[MAX], dp[MAX], q;
vector<int> ord, blocks[MAX];

bool cmp(int i, int j){ return x[i] < x[j]; }

void init(int n_, int l_, int x_[]){
  n = n_, L = l_;
  T = sqrt(n) + 1;
 
  for(int i = 0; i < n; i++)
    x[i] = x_[i];

  for(int i = 0; i < n; i++) 
      ord.push_back(i);
}
 
void buildBlock(int b){
  int s = sz(blocks[b]), lst = x[blocks[b].back()];

  for(int l = s - 1, r = s - 1; l >= 0; l--){
    int curId = blocks[b][l], curPos = x[curId];

    if(lst - curPos <= l){
      dp[curId] = 1;
      dist[curId] = curPos + L;

    }else{
      while(x[blocks[b][r]] - curPos > l) r--;

      dp[curId] = dp[blocks[b][r]] + 1;
      dist[curId] = dist[blocks[b][r]];
    }
  }
}

void build(){
  for(int i = 0; i <= (n - 1) / T; i++) 
      blocks[i].clear();

  sort(all(ord), cmp);

  for(int i = 0; i < n; i++){
    block[ord[i]] = i / T;
    blocks[i / T].push_back(ord[i]);
  }

  for(int i = 0; i <= (n - 1) / T; i++) 
    buildBlock(i);
}

int query(){
  int resp = 0;

  for(int i = 0, t = -1; i <= (n - 1) / T; i++){
    if(blocks[i].empty() || t >= x[blocks[i].back()]) continue;

    int l = 0, r = sz(blocks[i]) - 1, jump = 0;

    while(l <= r){
      int m = (l + r) >> 1;
      int curPos = x[blocks[i][m]];

      if(curPos > t) jump = m, l = m + 1;
      else r = m - 1;
    }

    resp += dp[blocks[i][jump]];
    t = dist[blocks[i][jump]]; 
  }

  return resp;
}

int update(int i, int y){ 
  if(q % T == 0) build();
  q++;

  //Remove from current block
  vector<int> aux;

  for(auto x : blocks[i]){
    if(x == i) continue;
    aux.push_back(x);
  }

  swap(aux, blocks[block[i]]);
  buildBlock(block[i]);

  //Add to new block
  aux.clear();

  int newBlock = 0;

  for(int j = 0; j <= (n - 1) / T; j++)
    if(blocks[j].size() && blocks[j].back() >= y){ newBlock = j; break; }

  aux.push_back(i);
  x[i] = y;

  vector<int> ret(sz(blocks[newBlock]) + 1);
  merge(aux.begin(), aux.end(), blocks[newBlock].begin(), blocks[newBlock].end(), ret.begin(), cmp);

  swap(ret, blocks[newBlock]);
  buildBlock(newBlock);

  return query();
}

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