제출 #1226480

#제출 시각아이디문제언어결과실행 시간메모리
1226480GabrielDigital Circuit (IOI22_circuit)C++20
18 / 100
397 ms14476 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...