Submission #1211527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211527		HappyCapybara	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	9090 ms	2884 KiB

elephants

#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;

int k = 400;
int n, l, t;
set<pair<int,int>> e;
vector<int> pos, eb;

struct bucket {
  set<pair<int,int>> es;
  unordered_map<int,pair<int,int>> res;

  bucket(){};
};

vector<bucket*> buckets;

void calc(bucket* b){
  vector<pair<int,int>> v;
  for (pair<int,int> el : b->es) v.push_back(el);
  if (!v.empty()) v.push_back({v.back().first+l+1, -1});
  int it = v.size()-1, next = v.size()-1;
  while (it != 0){
    it--;
    while (v[next-1].first > v[it].first+l) next--;
    if (v[next].second = -1) b->res[v[it].second] = {1, v[it].first+l};
    else b->res[v[it].second] = {1+b->res[v[next].second].first, b->res[v[next].second].second};
  }
}

void build(){
  int ct = 0, cb = 0;
  auto it = e.begin();
  buckets[0]->es.clear();
  buckets[0]->res.clear();
  while (it != e.end()){
    buckets[cb]->es.insert(*it);
    eb[it->second] = cb;
    it++;
    ct++;
    if (ct == k){
      ct = 0;
      cb++;
      buckets[cb]->es.clear();
      buckets[cb]->res.clear();
    }
  }
  for (auto b : buckets) calc(b);
}

int solve(){
  int ans = 0;
  auto cur = e.begin();
  while (cur != e.end()){
    pair<int,int> jump = buckets[eb[cur->second]]->res[cur->second];
    ans += jump.first;
    cur = e.upper_bound({jump.second, 1000000});
  }
  return ans;
}

void init(int N, int L, int X[]){
  n = N;
  l = L;
  pos.resize(n);
  for (int i=0; i<N; i++){
    pos[i] = X[i];
    e.insert({X[i], i});
  }
  eb.resize(n);
  for (int i=0; i<=n/k; i++) buckets.push_back(new bucket());
  build();
  t = 0;
}

int update(int i, int y){
  t++;
  if (t == 4*k){
    e.erase({pos[i], i});
    pos[i] = y;
    e.insert({pos[i], i});
    t = 0;
    build();
    return solve();
  }
  buckets[eb[i]]->es.erase({pos[i], i});
  calc(buckets[eb[i]]);
  e.erase({pos[i], i});
  pos[i] = y;
  e.insert({pos[i], i});
  int nb = 0;
  for (int pb = 1; pb < buckets.size(); pb++){
    if (!buckets[pb]->es.empty()){
      if (buckets[pb]->es.begin()->first <= pos[i]) nb = pb;
      else break;
    }
  }
  buckets[nb]->es.insert({pos[i], i});
  eb[i] = nb;
  calc(buckets[nb]);
  return solve();
}

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