Submission #1226480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226480		Gabriel	Digital Circuit (IOI22_circuit)	C++20	18 / 100	397 ms	14476 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
struct Nodo{
  long long Maneras, Posibilidades;
};
bool _1 = 1, _2 = 1, _rbol_de_segmentos = 1;
long long M_dulo = 1e9 + 2022;
long long Sumar(long long a, long long b){
  return (a % M_dulo + b % M_dulo) % M_dulo;
}
long long Restar(long long a, long long b){
  return ((a % M_dulo - b % M_dulo) % M_dulo + M_dulo) % M_dulo;
}
long long Multiplicar(long long a, long long b){
  return (a % M_dulo * b % M_dulo) % M_dulo;
}
Nodo operator+(const Nodo& a, const Nodo& b){
  Nodo Nuevo;
  Nuevo.Maneras = Sumar(Multiplicar(a.Maneras, b.Posibilidades), Multiplicar(b.Maneras, a.Posibilidades)) % M_dulo;
  Nuevo.Posibilidades = Multiplicar(2, Multiplicar(a.Posibilidades, b.Posibilidades));
  return Nuevo;
}
vector<Nodo> Puertas;
vector<int> Estado, Antecesor;
vector<Nodo> _rbol;
vector<bool> Invertir;
vector< vector<int> > Sucesores;
vector<int> _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa;
int n, m;
Nodo Nada;
void Propagar(long long p){
  if(Invertir[p]){
    Invertir[p] = -0;
    _rbol[p].Maneras = Restar(_rbol[p].Posibilidades, _rbol[p].Maneras);
    if(p * 2 < Invertir.size()) Invertir[p * 2] = !Invertir[p * 2];
    if(p * 2 + 1 < Invertir.size()) Invertir[p * 2 + 1] = !Invertir[p * 2 + 1];
  }
}
void Crear(int i, int d, int p){
  if(i == d){
    _rbol[p].Maneras = Estado[i];
    _rbol[p].Posibilidades = 1;
    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 Actualizar(int i, int d, int p, int I, int D){
  Propagar(p);
  if(i >= I and d <= D){
    _rbol[p].Maneras = Restar(_rbol[p].Posibilidades, _rbol[p].Maneras);
    if(i != d){
      Invertir[p * 2] = !Invertir[p * 2];
      Invertir[p * 2 + 1] = !Invertir[p * 2 + 1];
    }
    return;
  }
  if(i > D or d < I) return;
  int P = (i + d) / 2;
  Actualizar(i, P, p * 2, I, D);
  Actualizar(P + 1, d, p * 2 + 1, I, D);
  _rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
void Propagar_chafa(int i, int d, int p){
  if(Invertir[p]){
    Invertir[p] = -0;
    _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p] = d - i + 1 - _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p];
    if(p * 2 < Invertir.size()) Invertir[p * 2] = !Invertir[p * 2];
    if(p * 2 + 1 < Invertir.size()) Invertir[p * 2 + 1] = !Invertir[p * 2 + 1];
  }
}
void Crear_chafa(int i, int d, int p){
  if(i == d){
    _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p] = Estado[i];
    return;
  }
  int P = (i + d) / 2;
  Crear_chafa(i, P, p * 2);
  Crear_chafa(P + 1, d, p * 2 + 1);
  _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p] = _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p * 2] + _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p * 2 + 1];
}
void Actualizar_chafa(int i, int d, int p, int I, int D){
  Propagar_chafa(i, d, p);
  if(i >= I and d <= D){
    _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p] = d - i + 1 - _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p];
    if(i != d){
      Invertir[p * 2] = !Invertir[p * 2];
      Invertir[p * 2 + 1] = !Invertir[p * 2 + 1];
    }
    return;
  }
  if(i > D or d < I) return;
  int P = (i + d) / 2;
  Actualizar_chafa(i, P, p * 2, I, D);
  Actualizar_chafa(P + 1, d, p * 2 + 1, I, D);
  _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p] = _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p * 2] + _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[p * 2 + 1];
}
void Actualizar2(int p, int o){
  if(p == -1) return;
  if(p == o) Puertas[p].Maneras = Restar(Puertas[p].Posibilidades, Puertas[p].Maneras);
  else Puertas[p] = Puertas[Sucesores[p][0]] + Puertas[Sucesores[p][1]];
  Actualizar2(Antecesor[p], o);
}
void init(int N, int M, vector<int> P, vector<int> A){
  n = N;
  m = M;
  if(n > 1022 or m > 1022) _2 = 0;
  Estado = A;
  Sucesores.assign(n + m, {});
  if(n > 1) _1 = 0;
  for(int i = 1; i < n + m; i++){
    if(P[i] != (i - 1) / 2) _rbol_de_segmentos = 0;
  }
  vector<int> Grado(n + m, 0);
  Nada.Maneras = 0;
  Nada.Posibilidades = 1;
  Puertas.assign(n + m, Nada);
  for(int i = 0; i < n + m; i++){
    Antecesor.push_back(P[i]);
    if(i > 0){
      Grado[P[i]]++;
      if(Grado[P[i]] > 2){
        _2 = 0;
        _rbol_de_segmentos = 0;
        break;
      }
      Sucesores[P[i]].push_back(i);
    }
    if(i >= n){
      Puertas[i].Maneras = 1 - A[i - n];
      Puertas[i].Posibilidades = 1;
    }
  }
  Invertir.assign(m * 4 + 22, 0);
  if(_1){
    _rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa.assign(n * 4 + 22, 0);
    Crear_chafa(0, m - 1, 1);
    return;
  }
  if(_rbol_de_segmentos){
    _rbol.assign(m * 4 + 22, Nada);
    Crear(0, m - 1, 1);
    return;
  }
  if(_2){
    for(int i = 0; i < m; i++) Actualizar2(i + n, i + n);
    return;
  }
}
int q = 0;
int count_ways(int l, int r){
  if(_1){
    l--;
    r--;
    Actualizar_chafa(0, m - 1, 1, l, r);
    return (int)_rbol_chafa_que_ni_siquiera_es_necesario_para_sacar_la_primera_subtarea__pero_se_ve_mejor_que_hacer_una_fuerza_bruta_que_es_incluso_m_s_chafa[1] % M_dulo;
  }
  if(_rbol_de_segmentos){
    l -= n;
    r -= n;
    Actualizar(0, m - 1, 1, l, r);
    return (int)_rbol[1].Maneras % M_dulo;
  }
  if(_2){
    q++;
    if(q > 6) _2 = 0;
    for(; l <= r; l++) Actualizar2(l, l);
    return (int)Puertas[0].Maneras % M_dulo;
  }
  return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11