Submission #1114396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114396		PagodePaiva	Dancing Elephants (IOI11_elephants)	C++17	10 / 100	2 ms	6488 KiB

elephants

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

using namespace std;

int n, l;
const int N = 150010;
const int B = 3;
map <pair <int, int>, int> res, pai, bloco;
set <pair <int, int>> s;
int val[N];

void init(int NN, int L, int x[]){
  n = NN;
  l = L;
  res[{x[n-1], n-1}] = 1;
  pai[{x[n-1], n-1}] = 1e9+10;
  for(int i = 0;i < n;i++){
    int d = i/B;
    bloco[{x[i], i}] = d*B;
    val[i] = x[i];
  }
  s.insert({x[n-1], n-1});
  for(int i = n-2;i >= 0;i--){
    auto it = s.upper_bound({x[i]+l, 1e9});
    if(it == s.end()){
      res[{x[i], i}] = 1;
      pai[{x[i], i}] = 1e9+10;
    }
    else{
      pair <int, int> d = *it;
      res[{x[i], i}] = (bloco[d] != bloco[{x[i], i}] ? 1 : res[d]+1);
      pai[{x[i], i}] = (bloco[d] != bloco[{x[i], i}] ? d.first : pai[d]);
    }
    s.insert({x[i], i});
  }
  return;
}

void remover(int i, int y){
  int t = val[i];
  //cout << i << ' ' << y << '\n';
  auto it = s.find({val[i], i});
  int cu = bloco[{t, i}];
  while(bloco[{t, i}] == bloco[*it]){
    it++;
    if(it == s.end()) break;
  }
  s.erase({val[i], i});
  it--;
  pair <int, int> valor = *it;
  res.erase({val[i], i});
  pai.erase({val[i], i});
  bloco.erase({val[i], i});
  val[i] = y;
  it = s.find(valor);
  while(bloco[valor] == cu){
    //cout << valor.first << ' ' << valor.second << '\n';
    auto itt = s.upper_bound({valor.first+l, 1e9});
    if(itt == s.end()){
      res[valor] = 1;
      pai[valor] = 1e9+10;
      if(it == s.begin()) break;
      it--;
      valor = *it;
      //cout << valor.first << ' ' << valor.second << '\n';
      continue;
    }
    pair <int, int> d = *itt;
    if(bloco[d] != bloco[valor]){
      res[valor] = 1;
      pai[valor] = d.first;
    }
    else{
      res[valor] = res[d]+1;
      pai[valor] = pai[d];
    }
    if(it == s.begin()) break;
    it--;
    valor = *it;
  }
  cu = bloco[valor];
  while(bloco[valor] == cu){
    auto itt = s.upper_bound({valor.first+l, 1e9});
    if(itt == s.end()){
      res[valor] = 1;
      pai[valor] = 1e9+10;
      if(it == s.begin()) break;
      it--;
      valor = *it;
      continue;
    }
    pair <int, int> d = *itt;
    if(bloco[d] != bloco[valor]){
      res[valor] = 1;
      pai[valor] = d.first;
    }
    else{
      res[valor] = res[d]+1;
      pai[valor] = pai[d];
    }
    if(it == s.begin()) break;
    it--;
    valor = *it;
  }
}

void addd(int i, int y){
  val[i] = y;
  auto it = s.lower_bound({y, 0});
  if(it == s.begin()){
    bloco[{y, i}] = bloco[*it];
  }
  else{
    auto it2 = prev(it);
    bloco[{y, i}] = bloco[*it2];
  }
  int bl = bloco[{y, i}];
  s.insert({y, i});
  it = s.find({y, i});
  while(bloco[*it] == bl){
    it++;
    if(it == s.end()) break;
  }
  int tam = 0;
  it--;
  while(bloco[*it] == bl){
    tam++;
    if(it == s.begin()) break;
    it--;
  }
  if(tam > 2*B){
    tam = 0;
    while(bloco[*it] == bl and tam < B){
      tam++;
      it++;
    }
    while(bloco[*it] == bl){
      tam++;
      bloco[*it]++;
      it++;
    }
  }
  else{
    it++;
    if(it != s.end()){
       while(bloco[*it] == bl){
        it++;
        if(it == s.end()) break;
      }
    }
  }
  it--;
  pair <int, int> valor = *it;
  int cu = bloco[valor];
  it = s.find(valor);
  while(bloco[valor] == cu){
    auto itt = s.upper_bound({valor.first+l, 1e9});
    if(itt == s.end()){
      res[valor] = 1;
      pai[valor] = 1e9+10;
      if(it == s.begin()) break;
      it--;
      valor = *it;
      continue;
    }
    pair <int, int> d = *itt;
    if(bloco[d] != bloco[valor]){
      res[valor] = 1;
      pai[valor] = d.first;
    }
    else{
      res[valor] = res[d]+1;
      pai[valor] = pai[d];
    }
    if(it == s.begin()) break;
    it--;
    valor = *it;
  }
  cu = bloco[valor];
  while(bloco[valor] == cu){
    auto itt = s.upper_bound({valor.first+l, 1e9});
    if(itt == s.end()){
      res[valor] = 1;
      pai[valor] = 1e9+10;
      if(it == s.begin()) break;
      it--;
      valor = *it;
      continue;
    }
    pair <int, int> d = *itt;
    if(bloco[d] != bloco[valor]){
      res[valor] = 1;
      pai[valor] = d.first;
    }
    else{
      res[valor] = res[d]+1;
      pai[valor] = pai[d];
    }
    if(it == s.begin()) break;
    it--;
    valor = *it;
  }
  while(bloco[valor] == cu){
    auto itt = s.upper_bound({valor.first+l, 1e9});
    pair <int, int> d = *itt;
    if(itt == s.end()){
      res[valor] = 1;
      pai[valor] = 1e9+10;
      if(it == s.begin()) break;
      it--;
      valor = *it;
      continue;
    }
    if(bloco[d] != bloco[valor]){
      res[valor] = 1;
      pai[valor] = d.first;
    }
    else{
      res[valor] = res[d]+1;
      pai[valor] = pai[d];
    }
    if(it == s.begin()) break;
    it--;
    valor = *it;
  }
  return;
}

int update(int i, int y){
  /*for(auto [p, x] : pai){
    auto [val, i] = p;
    cout << val << ' ' << i << ' ' << x << ' ' << res[{val, i}] << endl;
  }*/
  remover(i, y);
  /*for(auto [p, x] : pai){
    auto [val, i] = p;
    cout << val << ' ' << i << ' ' << x << ' ' << res[{val, i}] << ' ' << bloco[{val, i}] << endl;
  }*/
  addd(i, y);
  /*for(auto [p, x] : pai){
    auto [val, i] = p;
    cout << val << ' ' << i << ' ' << x << ' ' << res[{val, i}] << ' ' << bloco[{val, i}] << endl;
  }*/
  int ans = 0;
  auto it = s.begin();
  while(it != s.end()){
    pair <int, int> aux = *it;
    ans += res[aux];
    int nx = pai[aux];
    it = s.lower_bound({nx, -1});
    //cout << pai[aux] << ' ';
  }
  return ans;
}

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