Submission #1293296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293296		julia_08	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	9090 ms	4900 KiB

elephants

#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

const int MAXN = 2e5 + 10;
const int INF = 1e9;

const int B = 100;
const int UPD = 10;

int x[MAXN], ind[MAXN];

pair<int, int> suf[MAXN];

multiset<pair<int, int>> ms;

vector<vector<pair<int, int>>> buckets;

int n, l;

int cnt_upd = 0;

void process(int id){

  // calcula sufixo de cada cara
  // suf[i] = {quantos intervalos preciso dentro desse bucket, extra}

  sort(buckets[id].begin(), buckets[id].end());

  int sz = (int) buckets[id].size();

  suf[buckets[id][sz - 1].second] = {1, l};

  int r = sz - 1;

  for(int i=(sz - 2); i>=0; i--){

    while(buckets[id][r].first - buckets[id][i].first > l) r--;

    int last = 0;

    if(r < sz - 1) last = suf[buckets[id][r + 1].second].first;

    int extra = l;

    if(r < sz - 1) extra = suf[buckets[id][r + 1].second].second + buckets[id][r + 1].first - buckets[id][i].first;

    suf[buckets[id][i].second] = {last + 1, extra};

  }

}

void create_buckets(){

  int cnt = 0;

  buckets.clear();
  buckets.push_back({});

  for(auto x : ms){

    if(cnt < B){

      buckets.back().push_back(x);
      cnt ++;

    } else{

      buckets.push_back({x});
      cnt = 1;

    }

    ind[x.second] = (int) buckets.size() - 1;

  }

  for(int i=0; i<buckets.size(); i++) process(i);

}

void refresh(){

  cnt_upd ++;

  if(cnt_upd == UPD){
    create_buckets();
    cnt_upd = 0;
  }

}

int find_bucket(int x){

  if(x <= buckets[0].back().first) return 0;

  for(int i=1; i<buckets.size(); i++){
    if(buckets[i - 1][0].first < x && x <= buckets[i].back().first){
      return i;
    }
  }

  return (int) buckets.size() - 1;

}

void remove(int id){

  int j = ind[id];

  for(int i=0; i<buckets[j].size(); i++){

    if(buckets[j][i].second == id){

      swap(buckets[j][i], buckets[j].back());
      buckets[j].pop_back();

      break;

    }

  }

  process(j);

  ms.erase({x[id], id});

}

void add(int id){

  int j = find_bucket(x[id]);
  ind[id] = j;

  buckets[j].push_back({x[id], id});
  process(j);

  ms.insert({x[id], id});

}

int query(){

  int ans = 0;

  int cur = buckets[0][0].second;

  int cnt = 0;

  while(x[cur] <= ms.rbegin()->first){

    ans += suf[cur].first;

    int nxt = x[cur] + suf[cur].second;
    auto pos = ms.upper_bound({nxt, INF});

    if(pos == ms.end()) break;
    cur = pos->second;

  }

  return ans;

}

void init(int n_, int l_, int x_[]){

  n = n_;
  l = l_;

  for(int i=0; i<n; i++) x[i] = x_[i];

  for(int i=0; i<n; i++) ms.insert({x[i], i});

  create_buckets();

  for(int i=0; i<buckets.size(); i++) process(i);

}

int update(int id, int y){

  // primeiro, tenho que tirar o i do x[i]

  remove(id);

  x[id] = y;

  add(id);

  refresh();

  return query();

}

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