Submission #1211533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211533		HappyCapybara	Dancing Elephants (IOI11_elephants)	C++20	26 / 100	9094 ms	2380 KiB

elephants

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

#define es first
#define res second

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

void calc(pair<set<pair<int,int>>, unordered_map<int,pair<int,int>>>& b){
  auto it = b.es.end();
  while (it != b.es.begin()){
    it--;
    auto next = b.es.upper_bound({it->first+l, 1000000});
    if (next == b.es.end()) b.res[it->second] = {1, it->first+l};
    else b.res[it->second] = {1+b.res[next->second].first, b.res[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);
  set<pair<int,int>> emptyset;
  unordered_map<int,pair<int,int>> emptymap;
  for (int i=0; i<=n/k; i++) buckets.push_back({emptyset, emptymap});
  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