Submission #1245709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245709		Gabriel	Seats (IOI18_seats)	C++20	11 / 100	4097 ms	79216 KiB

seats

#include "seats.h"
#include "bits/stdc++.h"
using namespace std;
vector< pair<int, int> > Sillas;
int n;
bool Cuatro = 0;
struct Respuesta{
  pair<int, int> Arribita, Abajito;
};
vector<Respuesta> Anteriores;
vector<int> _rbol, Respuestas, Propagar;
void Crear(int i, int d, int p){
  if(i == d){
    _rbol[p] = Respuestas[i];
    return;
  }
  int P = (i + d) / 2;
  Crear(i, P, p * 2);
  Crear(P + 1, d, p * 2 + 1);
  //_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
void Propagante(int i, int d, int p){
  _rbol[p] += Propagar[p] * (d - i + 1);
  if(i == d) Respuestas[i] += Propagar[p];
  if(p * 2 < _rbol.size() and i != d) Propagar[p * 2] += Propagar[p];
  if(p * 2 + 1 < _rbol.size() and i != d) Propagar[p * 2 + 1] += Propagar[p];
  Propagar[p] = -0;
}
int Consulta(int i, int d, int p, int I, int D){
  Propagante(i, d, p);
  if(i >= I and d <= D) return _rbol[p];
  if(i > D or d < I) return -0;
  int P = (i + d) / 2;
  return Consulta(i, P, p * 2, I, D) + Consulta(P + 1, d, p * 2 + 1, I, D);
}
void Actualizar(int i, int d, int p, int I, int D, int v){
  Propagante(i, d, p);
  if(i >= I and d <= D){
    Propagar[p] += v;
    Propagante(i, d, p);
    return;
  }
  if(i > D or d < I) return;
  int P = (i + d) / 2;
  Actualizar(i, P, p * 2, I, D, v);
  Actualizar(P + 1, d, p * 2 + 1, I, D, v);
  //_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
  n = h * w;
  if(n > 1e4) Cuatro = 1;
  Sillas.assign(n, {});
  for(int i = 0; i < n; i++){
    Sillas[i] = {r[i], c[i]};
  }
  //Cuatro = 1;
  if(Cuatro){
    pair<int, int> Arriba, Abajo;
    int r1 = 0;
    for(int i = 0; i < n; i++){
      //cerr<<i<<" "<<n<<"\n";
      if(i == 0){
        r1++;
        Arriba.first = Sillas[i].first;
        Arriba.second = Sillas[i].second;
        Abajo.first = Sillas[i].first;
        Abajo.second = Sillas[i].second;
        Respuestas.push_back(r1);
        continue;
      }
      if(Sillas[i].first < Arriba.first) Arriba.first = Sillas[i].first;
      if(Sillas[i].first > Abajo.first) Abajo.first = Sillas[i].first;
      if(Sillas[i].second < Arriba.second) Arriba.second = Sillas[i].second;
      if(Sillas[i].second > Abajo.second) Abajo.second = Sillas[i].second;
      if(i + 1 == (Abajo.first - Arriba.first + 1) * (Abajo.second - Arriba.second + 1)) r1++;
      Respuesta Anterior;
      Anterior.Abajito = Abajo;
      Anterior.Arribita = Arriba;
      Anteriores.push_back(Anterior);
      //cerr<<r1<<" ";
      Respuestas.push_back(r1);
    }
    _rbol.assign(n * 4 + 22, 0);
    Propagar.assign(n * 4 + 22, 0);
    Crear(0, n - 1, 1);
    /*cerr<<"\n";
    for(int i = 0; i < n; i++) cerr<<Respuestas[i]<<" ";
    cerr<<"\n";
    for(int i = 0; i < n; i++) cerr<<Consulta(0, n - 1, 1, i, i)<<" ";
    cerr<<"\n";*/
  }
}
int swap_seats(int a, int b){
  if(Cuatro){
    swap(Sillas[a], Sillas[b]);
    if(a > b) swap(a, b);
    int Respuesta_actual = 0;
    a--;
    pair<int, int> Arriba, Abajo;
    if(a > -1){
      Respuesta_actual = Consulta(0, n - 1, 1, a, a);
      Arriba = Anteriores[a].Arribita;
      Abajo = Anteriores[a].Abajito;
    }
    for(int i = a + 1; i < b; i++){
      if(i == 0){
        Respuesta_actual++;
        Arriba.first = Sillas[i].first;
        Arriba.second = Sillas[i].second;
        Abajo.first = Sillas[i].first;
        Abajo.second = Sillas[i].second;
        Anteriores[i].Arribita = Arriba;
        Anteriores[i].Abajito = Abajo;
        if(i == b - 1) Actualizar(0, n - 1, 1, i, n - 1, Respuesta_actual - Consulta(0, n - 1, 1, i, i));
        else Actualizar(0, n - 1, 1, i, i, Respuesta_actual - Consulta(0, n - 1, 1, i, i));
        continue;
      }
      if(Sillas[i].first < Arriba.first) Arriba.first = Sillas[i].first;
      if(Sillas[i].first > Abajo.first) Abajo.first = Sillas[i].first;
      if(Sillas[i].second < Arriba.second) Arriba.second = Sillas[i].second;
      if(Sillas[i].second > Abajo.second) Abajo.second = Sillas[i].second;
      Anteriores[i].Arribita = Arriba;
      Anteriores[i].Abajito = Abajo;
      if(i + 1 == (Abajo.first - Arriba.first + 1) * (Abajo.second - Arriba.second + 1)) Respuesta_actual++;
      if(i == b - 1) Actualizar(0, n - 1, 1, i, n - 1, Respuesta_actual - Consulta(0, n - 1, 1, i, i));
      else Actualizar(0, n - 1, 1, i, i, Respuesta_actual - Consulta(0, n - 1, 1, i, i));
    }
    return Consulta(0, n - 1, 1, n - 1, n - 1);
  }
  swap(Sillas[a], Sillas[b]);
  pair<int, int> Arriba, Abajo;
  int r = 0;
  for(int i = 0; i < n; i++){
    if(i == 0){
      r++;
      Arriba.first = Sillas[i].first;
      Arriba.second = Sillas[i].second;
      Abajo.first = Sillas[i].first;
      Abajo.second = Sillas[i].second;
      continue;
    }
    if(Sillas[i].first < Arriba.first) Arriba.first = Sillas[i].first;
    if(Sillas[i].first > Abajo.first) Abajo.first = Sillas[i].first;
    if(Sillas[i].second < Arriba.second) Arriba.second = Sillas[i].second;
    if(Sillas[i].second > Abajo.second) Abajo.second = Sillas[i].second;
    if(i + 1 == (Abajo.first - Arriba.first + 1) * (Abajo.second - Arriba.second + 1)) r++;
  }
  return r;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30