제출 #1226467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1226467		Gabriel	Digital Circuit (IOI22_circuit)	C++20	18 / 100	394 ms	6300 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;
vector<int> Estado;
vector<Nodo> _rbol;
vector<bool> Invertir;
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;
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, a.Posibilidades), Multiplicar(b.Maneras, b.Posibilidades)) % M_dulo;
  Nuevo.Posibilidades = Multiplicar(2, Multiplicar(a.Posibilidades, b.Posibilidades));
  return Nuevo;
}
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 init(int N, int M, vector<int> P, vector<int> A){
  n = N;
  m = M;
  Estado = A;
  if(n > 1) _1 = 0;
  for(int i = 1; i < n + m; i++){
    if(P[i] != (i - 1) / 2) _rbol_de_segmentos = 0;
  }
  Nada.Maneras = 0;
  Nada.Posibilidades = 0;
  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);
  }
}
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;
  }
  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