제출 #1114385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1114385		PagodePaiva	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	55 ms	21068 KiB

elephants

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

using namespace std;

int n, l;
const int N = 150010;
const int B = 300;
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++){
    bloco[{x[i], i}] = (i/B)*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];
  auto it = s.find({val[i], i});
  while(bloco[{t, i}] == bloco[*it]){
    it++;
    if(it == s.end()) break;
  }
  it--;
  pair <int, int> valor = *it;
  res.erase({val[i], i});
  pai.erase({val[i], i});
  bloco.erase({val[i], i});
  s.erase({val[i], i});
  val[i] = y;
  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;
  }
  if(it == s.begin()) return;
  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{
     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;
  }
  if(it == s.begin()) return;
  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;
  }
  if(it == s.begin()) return;
  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}] << endl;
  //}
  addd(i, y);
  //for(auto [p, x] : pai){
    //auto [val, i] = p;
    ///cout << val << ' ' << i << ' ' << x << ' ' << res[{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: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3