Submission #1211519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211519		HappyCapybara	Dancing Elephants (IOI11_elephants)	C++20	97 / 100	9091 ms	24408 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){
  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);
  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 == 2*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() && buckets[pb]->es.begin()->first <= pos[i]) nb = pb;
  }
  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: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3