Problema A
Pensamento
Este é um problema de aquecimento bastante direto. A tarefa consiste em imprimir um padrão específico de caracteres, que pode ser facilmente reproduzido usando laços de repetição e chamadas de função de impressão. A complexidade reside apenas em replicar o padrão exato conforme as especificações, com base no valor de entrada.
Código
#include <cstdio> // Para printf e scanf
int main() {
int numPontos;
// Lê o número inteiro que determina a quantidade de pontos entre os 'o's.
scanf("%d", &numPontos);
// Primeira linha do padrão
printf("ooo");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("ooo");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("ooo");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("ooo\n");
// Segunda linha do padrão
printf("..o");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("o.o");
for (int k = 0; k < numPontos; ++k) printf(".");
printf(".o.");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("o.o\n");
// Terceira linha do padrão
printf("ooo");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("o.o");
for (int k = 0; k < numPontos; ++k) printf(".");
printf(".o.");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("ooo\n");
// Quarta linha do padrão
printf("o..");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("o.o");
for (int k = 0; k < numPontos; ++k) printf(".");
printf(".o.");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("o.o\n");
// Quinta linha do padrão
printf("ooo");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("ooo");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("ooo");
for (int k = 0; k < numPontos; ++k) printf(".");
printf("ooo\n");
return 0;
}
Problema B
Pensamento
A abordagem para este problema é identificar um padrão matemático através da observação de casos iniciais ou pela construção de uma tabela de resultados. Geralmente, problemas com essa característica envolvem combinatória ou sequências numéricas. Neste caso, a solução converge para o uso de coeficientes binomiais, especificamente \\(C(n+m, m)\\), calculado modulo um grande número primo. Para otimizar, pré-calculamos os coeficientes binomiais (triângulo de Pascal) até os limites necessários.
Código
#include <cstdio> // Para scanf e printf
#include <algorithm> // Para std::min
const int MODULO_BASE = 1000000007; // O módulo para os cálculos
const int MAX_SOMA = 4007; // Soma máxima de n+m
const int MAX_M = 2007; // Valor máximo para m
int coeficientesBinomiais[MAX_SOMA][MAX_M]; // Tabela para C(i, j)
int main() {
// Pré-computa os coeficientes binomiais (Triângulo de Pascal)
// C[i][j] = C[i-1][j] + C[i-1][j-1]
for (int i = 0; i < MAX_SOMA; ++i) {
coeficientesBinomiais[i][0] = 1; // C(i, 0) é sempre 1
for (int j = 1; j <= std::min(i, MAX_M - 1); ++j) {
coeficientesBinomiais[i][j] = (coeficientesBinomiais[i - 1][j] + coeficientesBinomiais[i - 1][j - 1]) % MODULO_BASE;
}
}
int valN, valM;
// Continua lendo entradas até o fim do arquivo (EOF)
while (scanf("%d%d", &valN, &valM) != EOF) {
// Calcula o resultado usando a fórmula encontrada e o módulo
// O termo (coeficientesBinomiais[valN + valM][valM] - 1)
// é multiplicado por si mesmo e o resultado é ajustado pelo módulo.
// O -1 é aplicado porque uma das combinações não é válida ou é a base.
long long temp = (long long)coeficientesBinomiais[valN + valM][valM] - 1;
long long resultado = (temp * temp) % MODULO_BASE;
printf("%lld\n", resultado);
}
return 0;
}
Problema C
Pensamento
Este problema é resolvido através de uma análise simples dos exemplos fornecidos. Geralmente, isso indica uma relação direta ou uma lógica condicional básica entre as entradas. Neste caso, a saída é o maior dos dois valores de entrada ou um deles mais um, dependendo de qual é maior. Isso sugere uma regra específica que pode ser inferida sem a necessidade de algoritmos compplexos.
Código
#include <cstdio> // Para scanf e printf
int main() {
int altura, largura;
// Loop para ler múltiplos casos de teste até o fim do arquivo (EOF)
while (scanf("%d%d", &altura, &largura) != EOF) {
// A lógica é verificar qual valor é maior e retornar um resultado com base nisso.
// Se 'altura' for maior que 'largura', a resposta é 'altura'.
// Caso contrário (se 'largura' for maior ou igual a 'altura'), a resposta é 'largura + 1'.
printf("%d\n", altura > largura ? altura : largura + 1);
}
return 0;
}
Problema E
Pensamento
O problema envolve o cálculo do número de componentes conectados em uma grade de \\(N \times M\\) células, onde linhas horizontais e verticais são adicionadas. Inicialmente, a grade tem \\(N \times M\\) componentes conectados. Quando uma linha horizontal é adicionada (que ainda não existia), ela divide \\(M\\) colunas, conectando \\(M-1\\) pares de células adjacentes, resultando em uma redução de \\(M-1\\) componentes conectados. Enalogamente, uma linha vertical reduz \\(N-1\\) componentes.
Para o caso em que tanto linhas horizontais quanto verticais estão presentes, precisamos aplicar o princípio da inclusão-exclusão. As intersecções das linhas são contadas duplamente como reduções. Se \\(H\\) linhas horizontais únicas e \\(W\\) linhas verticais únicas foram adicionadas, o número de intersecções (e, portanto, o número de componentes a serem adicionados de volta) é \\((H-1) \times (W-1)\\), se \\(H, W \ge 1\\).
A fórmula para o número de componentes conectados seria: \\[ N \times M - (H \times (M-1)) - (W \times (N-1)) + ((H-1) \times (W-1)) \\] Onde \\(H\\) é o número de linhas horizontais únicas ativas e \\(W\\) é o número de linhas verticais únicas ativas. Para gerenciar a adição de linhas em intervalos (e garantir que contamos apenas linhas únicas), utilizamos uma Segment Tree com compressão de coordenadas. A Segment Tree armazena a soma total das "coberturas" (linhas ou colunas únicas marcadas como ativas) para cada dimensão, permitindo atualizações e consultas eficientes em intervalos.
Código
#include <cstdio> // Para scanf e printf
#include <algorithm> // Para std::sort, std::unique, std::lower_bound
// Definindo constantes para o problema
const int MAX_COORD_VAL = 200000 + 7; // Valor máximo para N ou M, e para coordenadas
const long long INF_LL = 0x3f3f3f3f3f3f3f3fLL; // Valor infinito para long long
// Arrays para a Segment Tree
bool propagacaoLenta[2][MAX_COORD_VAL * 4]; // Lazy flag: [0] para horizontal, [1] para vertical
long long coberturaSegmento[2][MAX_COORD_VAL * 4]; // Soma total de segmentos cobertos
int coordsUnicas[MAX_COORD_VAL * 2]; // Coordenadas discretizadas
int linhasTotal, colunasTotal, numConsultas, contaCoords; // N, M, Q e contador de coordenadas únicas
int tipoOperacao[MAX_COORD_VAL], inicioIntervalo[MAX_COORD_VAL], fimIntervalo[MAX_COORD_VAL]; // Dados das operações
// Função para empurrar o estado 'lazy' para os filhos na Segment Tree
void empurrarParaBaixo(int noAtual, int inicio, int fim, int id) {
if (!propagacaoLenta[id][noAtual]) return; // Não há propagação pendente
propagacaoLenta[id][noAtual] = false; // Limpa a flag atual
propagacaoLenta[id][noAtual * 2] = propagacaoLenta[id][noAtual * 2 + 1] = true; // Marca filhos como lazy
int meio = (inicio + fim) / 2;
coberturaSegmento[id][noAtual * 2] = (long long)coordsUnicas[meio + 1] - coordsUnicas[inicio];
coberturaSegmento[id][noAtual * 2 + 1] = (long long)coordsUnicas[fim + 1] - coordsUnicas[meio + 1];
}
// Função para atualizar o valor do nó pai a partir dos filhos
void atualizarNoPai(int noAtual, int id) {
coberturaSegmento[id][noAtual] = coberturaSegmento[id][noAtual * 2] + coberturaSegmento[id][noAtual * 2 + 1];
}
// Constrói a Segment Tree
void construir(int noAtual, int inicio, int fim) {
for (int i = 0; i < 2; ++i) { // Inicializa para horizontal e vertical
coberturaSegmento[i][noAtual] = 0;
propagacaoLenta[i][noAtual] = false;
}
if (inicio == fim) return;
int meio = (inicio + fim) / 2;
construir(noAtual * 2, inicio, meio);
construir(noAtual * 2 + 1, meio + 1, fim);
}
// Atualiza um intervalo na Segment Tree
void atualizar(int noAtual, int inicio, int fim, int L, int R, int id) {
// Se o segmento atual está completamente dentro do intervalo de atualização [L, R]
if (inicio == L && fim == R) {
coberturaSegmento[id][noAtual] = (long long)coordsUnicas[R + 1] - coordsUnicas[L];
propagacaoLenta[id][noAtual] = true;
return;
}
empurrarParaBaixo(noAtual, inicio, fim, id); // Propaga lazy para baixo
int meio = (inicio + fim) / 2;
if (R <= meio) { // Intervalo de atualização está no filho esquerdo
atualizar(noAtual * 2, inicio, meio, L, R, id);
} else if (L > meio) { // Intervalo de atualização está no filho direito
atualizar(noAtual * 2 + 1, meio + 1, fim, L, R, id);
} else { // Intervalo de atualização se sobrepõe a ambos os filhos
atualizar(noAtual * 2, inicio, meio, L, meio, id);
atualizar(noAtual * 2 + 1, meio + 1, fim, meio + 1, R, id);
}
atualizarNoPai(noAtual, id); // Atualiza o nó pai
}
// Retorna o índice da coordenada discretizada
int obterIndiceCoordenada(int valor) {
return std::lower_bound(coordsUnicas + 1, coordsUnicas + contaCoords + 1, valor) - coordsUnicas;
}
int main() {
// Loop para processar múltiplos casos de teste
while (scanf("%d%d%d", &linhasTotal, &colunasTotal, &numConsultas) != EOF) {
contaCoords = 0;
// Armazena todas as coordenadas relevantes (início e fim+1 de cada intervalo)
for (int i = 1; i <= numConsultas; ++i) {
scanf("%d%d%d", &tipoOperacao[i], &inicioIntervalo[i], &fimIntervalo[i]);
coordsUnicas[++contaCoords] = inicioIntervalo[i];
coordsUnicas[++contaCoords] = fimIntervalo[i] + 1;
}
// Discretiza as coordenadas: ordena e remove duplicatas
std::sort(coordsUnicas + 1, coordsUnicas + contaCoords + 1);
contaCoords = std::unique(coordsUnicas + 1, coordsUnicas + contaCoords + 1) - coordsUnicas - 1;
// Constrói a Segment Tree com as coordenadas discretizadas
construir(1, 1, contaCoords);
// Processa cada consulta
for (int i = 1; i <= numConsultas; ++i) {
// Converte os intervalos originais para os índices discretizados
int L_disc = obterIndiceCoordenada(inicioIntervalo[i]);
int R_disc = obterIndiceCoordenada(fimIntervalo[i] + 1);
// Atualiza a Segment Tree (0 para horizontal, 1 para vertical)
atualizar(1, 1, contaCoords, L_disc, R_disc - 1, tipoOperacao[i] - 1);
// Calcula a resposta usando o princípio da inclusão-exclusão
long long hUnicas = coberturaSegmento[0][1]; // Total de linhas horizontais únicas
long long wUnicas = coberturaSegmento[1][1]; // Total de linhas verticais únicas
long long resultado = 1LL * linhasTotal * colunasTotal;
resultado -= hUnicas * (colunasTotal - 1);
resultado -= wUnicas * (linhasTotal - 1);
// Adiciona de volta as intersecções, se houver
if (hUnicas > 0 && wUnicas > 0) {
resultado += (hUnicas - 1) * (wUnicas - 1);
}
printf("%lld\n", resultado);
}
}
return 0;
}
Problema H
Pensamento
Dada a restrição de que a diferença entre os pontos finais de uma consulta (\\(r-l\\)) é sempre menor ou igual a 2, podemos empregar uma estratégia eficiente utilizando múltiplas Árvores de Fenwick (BITs). A ideia é manter uma BIT separada para cada possível comprimento de intervalo que pode ser consultado:
- Uma BIT para intervalos de comprimento 0 (ou seja, \\(l=r\\), um único ponto).
- Uma BIT para intervalos de comprimento 1 (ou seja, \\(r=l+1\\)).
- Uma BIT para intervalos de comprimento 2 (ou seja, \\(r=l+2\\)).
Quando um novo intervalo \\([L, R]\\) é inserido (operação tipo 1): - Para a BIT de comprimento 0, ele contribui para todos os pontos \\(i\\) no intervalo \\([L, R]\\). Usamos uma técnica de diferença: adicionamos 1 em \\(L\\) e subtraímos 1 em \\(R+1\\).
- Para a BIT de comprimento 1, ele contribui para todos os inícios \\(i\\) de intervalos de comprimento 1 (i.e., \\([i, i+1]\\)) dentro de \\([L, R]\\). Assim, os inícios são de \\(L\\) até \\(R-1\\). Adicionamos 1 em \\(L\\) e subtraímos 1 em \\(R\\).
- Para a BIT de comprimento 2, ele contribui para todos os inícios \\(i\\) de intervalos de comprimento 2 (i.e., \\([i, i+2]\\)) dentro de \\([L, R]\\). Os inícios são de \\(L\\) até \\(R-2\\). Adicionamos 1 em \\(L\\) e subtraímos 1 em \\(R-1\\).
Para uma consulta (operação tipo 2) que pede o número de intervalos que cobrem \\([l, r]\\), calculamos o comprimento \\(k = r-l\\) e consultamos a BIT correspondente no índice \\(l\\). As BITs permitem atualizações e consultas em tempo logarítmico, tornando esta abordagme eficiente. ### Código
#include <cstdio> // Para entrada/saída (scanf, printf)
#include <cstring> // Para memset (opcional, pode ser substituído por laço)
const int MAX_VAL = 100000 + 7; // Tamanho máximo do array N
int arvoreFenwick[3][MAX_VAL]; // Três Árvores de Fenwick (BITs) para comprimentos 0, 1 e 2
int tamanhoArray; // Representa 'N' no problema
int numConsultas; // Representa 'Q' no problema
// Função de leitura rápida para inteiros
inline int lerInteiro() {
int valor = 0;
char caractere = getchar();
bool negativo = false;
while (caractere < '0' || caractere > '9') {
if (caractere == '-') negativo = true;
caractere = getchar();
}
while (caractere >= '0' && caractere <= '9') {
valor = (valor << 3) + (valor << 1) + caractere - '0';
caractere = getchar();
}
return negativo ? -valor : valor;
}
// Adiciona um valor a uma posição na Árvore de Fenwick
void atualizarFenwick(int indice, int idBit, int val) {
while (indice <= tamanhoArray) {
arvoreFenwick[idBit][indice] += val;
indice += (indice & -indice); // Move para o próximo pai
}
}
// Consulta a soma prefixada até uma posição na Árvore de Fenwick
int consultarFenwick(int indice, int idBit) {
int soma = 0;
while (indice > 0) {
soma += arvoreFenwick[idBit][indice];
indice -= (indice & -indice); // Move para o próximo pai
}
return soma;
}
int main() {
// Processa múltiplos casos de teste
while (scanf("%d%d", &tamanhoArray, &numConsultas) != EOF) {
// Inicializa as Árvores de Fenwick para cada caso de teste
// A dimensão 0-2 é para os comprimentos de intervalo 0, 1, 2.
for (int i = 0; i < 3; ++i) {
for (int j = 0; j <= tamanhoArray; ++j) {
arvoreFenwick[i][j] = 0;
}
}
// Processa cada consulta
while (numConsultas--) {
int tipoOp = lerInteiro();
int inicio = lerInteiro();
int fim = lerInteiro();
if (tipoOp == 1) { // Operação de inserção
// Contribuição para intervalos de comprimento 0 ([inicio, inicio])
atualizarFenwick(inicio, 0, 1);
if (fim + 1 <= tamanhoArray) atualizarFenwick(fim + 1, 0, -1);
// Contribuição para intervalos de comprimento 1 ([inicio, inicio+1])
if (inicio <= fim - 1) {
atualizarFenwick(inicio, 1, 1);
if (fim <= tamanhoArray) atualizarFenwick(fim, 1, -1);
}
// Contribuição para intervalos de comprimento 2 ([inicio, inicio+2])
if (inicio <= fim - 2) {
atualizarFenwick(inicio, 2, 1);
if (fim - 1 <= tamanhoArray) atualizarFenwick(fim - 1, 2, -1);
}
} else { // Operação de consulta
// O comprimento do intervalo é 'fim - inicio'.
// Consultamos a BIT correspondente no índice 'inicio'.
printf("%d\n", consultarFenwick(inicio, fim - inicio));
}
}
}
return 0;
}
Problema J
Pensamento
Este problema envolve a travessia de uma árvore usando Busca em Profundidade (DFS) para calcular uma soma acumulada (contribuição) para cada nó. A "contribuição" de um nó \\(u\\) para \\(f_u\\) (a soma do caminho da raiz até \\(u\\)) depende da frequência do valor \\(a[u]\\) no caminho que leva ao próprio \\(u\\).
Durante a DFS, mantemos três informações importantes para cada valor \\(a[i]\\):
freqValores[x]: Conta quantas vezes o valor \\(x\\) apareceu no caminho atual da raiz até o nó em processamento.contDistintos: O número total de valores distintos no caminho atual da raiz até o nó em processamento.ultVisitaDistinta[x]: Registra o valor decontDistintosna última vez que o valor \\(x\\) apareceu no caminho como um elemento distinto.
A contribuição de \\(u\\) é calculada da seguinte forma:
- Primeira ocorrência de \\(a[u]\\) no caminho: A contribuição é
contDistintos(o número de valores distintos antes de adicionar \\(a[u]\\), mais 1 pela adição de \\(a[u]\\)). - Segunda ocorrência de \\(a[u]\\): A contribuição é
contDistintos - ultVisitaDistinta[a[u]] + 1. Isso representa o número de novos valores distintos adicionados desde a última aparição de \\(a[u]\\), mais 1 para o par \\((a[u], a[u]))\\). - Mais de duas ocorrências de \\(a[u]\\): A contribuição é
contDistintos - ultVisitaDistinta[a[u]]. Representa apenas os novos valores distintos desde a última aparição de \\(a[u]\\).
É crucial que, ao retroceder na DFS, "desfaçamos" as mudanças feitas pelo nó \\(u\\) no freqValores, contDistintos e ultVisitaDistinta para que o estado seja correto para os irmãos e outros ramos da árvore. ### Código
#include <cstdio> // Para scanf e printf
#include <vector> // Para std::vector
#include <cassert> // Para assert (verificações de sanidade)
const int MAX_NOS = 100000 + 7; // Limite máximo de nós na árvore
int resultados[MAX_NOS]; // Armazena a soma final para cada nó
int somaCaminhoAtual; // Soma acumulada de contribuições no caminho da DFS
int numNos; // Número total de nós na árvore
int contDistintosNoCaminho; // Contador de valores distintos no caminho atual
int valoresNos[MAX_NOS]; // Valor 'a[i]' para cada nó 'i'
int freqValores[MAX_NOS]; // Frequência de cada valor no caminho atual
int ultVisitaDistinta[MAX_NOS]; // 'contDistintosNoCaminho' quando um valor foi visto pela última vez
// Estrutura para representar as arestas da árvore
struct Aresta {
int destino;
};
std::vector<Aresta> listaAdj[MAX_NOS]; // Lista de adjacência para a árvore
// Função de Busca em Profundidade (DFS)
void realizarDFS(int u) {
int contribuicaoNodal = 0; // Contribuição do nó 'u' para a soma do caminho
// Calcula a contribuição baseada na frequência de a[u] no caminho
if (!freqValores[valoresNos[u]]) { // Primeira vez que a[u] aparece no caminho
contribuicaoNodal = contDistintosNoCaminho;
contDistintosNoCaminho++; // Incrementa o contador de distintos
} else if (freqValores[valoresNos[u]] == 1) { // Segunda vez que a[u] aparece
contribuicaoNodal = contDistintosNoCaminho - ultVisitaDistinta[valoresNos[u]] + 1;
} else { // Mais de duas vezes que a[u] aparece
contribuicaoNodal = contDistintosNoCaminho - ultVisitaDistinta[valoresNos[u]];
}
resultados[u] = somaCaminhoAtual + contribuicaoNodal; // Calcula o resultado final para o nó 'u'
// Armazena o estado atual antes de prosseguir
int estadoAntigoUltimaVisita = ultVisitaDistinta[valoresNos[u]];
ultVisitaDistinta[valoresNos[u]] = contDistintosNoCaminho; // Atualiza 'ultVisitaDistinta'
somaCaminhoAtual += contribuicaoNodal; // Adiciona a contribuição à soma do caminho
freqValores[valoresNos[u]]++; // Incrementa a frequência de a[u]
// Percorre os filhos do nó 'u'
for (const auto& aresta : listaAdj[u]) {
realizarDFS(aresta.destino);
}
// Ao retroceder (backtrack), desfaz as mudanças feitas pelo nó 'u'
somaCaminhoAtual -= contribuicaoNodal; // Remove a contribuição
freqValores[valoresNos[u]]--; // Decrementa a frequência
if (freqValores[valoresNos[u]] == 0) { // Se o valor não está mais no caminho, decrementa distintos
contDistintosNoCaminho--;
}
ultVisitaDistinta[valoresNos[u]] = estadoAntigoUltimaVisita; // Restaura 'ultVisitaDistinta'
}
int main() {
// Processa múltiplos casos de teste
while (scanf("%d", &numNos) != EOF) {
// Assertions para validação de entrada (podem ser removidas em produção)
assert(numNos >= 1 && numNos <= 100000);
// Limpa e inicializa variáveis para o novo caso de teste
somaCaminhoAtual = 0;
contDistintosNoCaminho = 0;
for (int i = 1; i <= numNos; ++i) {
listaAdj[i].clear(); // Limpa a lista de adjacência
freqValores[i] = 0;
resultados[i] = 0;
ultVisitaDistinta[i] = 0;
}
// Constrói a árvore lendo os pais de cada nó (de 2 a N)
for (int i = 2; i <= numNos; ++i) {
int paiNo;
scanf("%d", &paiNo);
assert(paiNo >= 1 && paiNo <= numNos && paiNo != i); // Validação
listaAdj[paiNo].push_back({i}); // Adiciona aresta do pai para o filho
}
// Lê os valores 'a[i]' para cada nó
for (int i = 1; i <= numNos; ++i) {
scanf("%d", &valoresNos[i]);
assert(valoresNos[i] >= 1 && valoresNos[i] <= numNos); // Validação
}
// Inicia a DFS a partir do nó 1 (raiz)
realizarDFS(1);
// Imprime os resultados para os nós de 2 a N
for (int i = 2; i <= numNos; ++i) {
printf("%d\n", resultados[i]);
}
}
return 0;
}
Problema K
Pensamento
Este problema pode ser resolvido eficientemente utilizando a técnica de soma de prefixos. Primeiro, calculamos as somas de prefixo para o array \\(A\\). Isso nos permite obter a soma de qualquer subsegmento de \\(A\\) em tempo constante.
O objetivo é calcular uma soma total que envolve os elementos de \\(A\\) e \\(B\\). Para cada elemento \\(b_i\\) do array \\(B\\), ele contribui para a soma total multiplicando-se pela soma de um intervalo específico do array \\(A\\). Este intervalo é \\([L-i, R-i]\\), onde \\(L\\) e \\(R\\) são os limites dados no problema (que são ajustados por 2 antes de serem usados).
Para cada \\(b_i\\):
- Determinamos o intervalo efetivo \\([l, r]\\) no array \\(A\\), considerando \\(l = \max(1, L-i)\\) e \\(r = \min(N+1, R-i)\\).
- Verificamos se o intervalo \\([l, r]\\) é válido (ou seja, se \\(l \le r\\)).
- Se for válido, calculamos a soma do subsegmento de \\(A\\) como \\(\text{somaPrefixosA}[r] - \text{somaPrefixosA}[l-1]\\).
- Multiplicamos essa soma por \\(b_i\\) e adicionamos ao resultado final, aplicando a operação de módulo em cada passo para evitar overflow e manter o resultado dentro dos limites especificados.
É importante notar que os índices \\(L\\) e \\(R\\) recebem um ajuste inicial de \\(+2\\) no código original, o que deve ser mantido na reimplementação para corresponder à lógica do problema original. ### Código
#include <cstdio> // Para scanf e printf
#include <algorithm> // Para std::max, std::min
const int MODULO_BASE = 1000000007; // O módulo para todos os cálculos
const int MAX_LEN = 500000 + 7; // Tamanho máximo para os arrays A e B
long long somaPrefixosA[MAX_LEN]; // Array para as somas de prefixo de 'arrayA'
long long arrayA[MAX_LEN]; // O primeiro array de entrada
long long arrayB[MAX_LEN]; // O segundo array de entrada
int main() {
int tamA, tamB, limiteEsquerdo, limiteDireito;
// Loop para processar múltiplos casos de teste
while (scanf("%d%d%d%d", &tamA, &tamB, &limiteEsquerdo, &limiteDireito) != EOF) {
// Ajuste dos limites L e R conforme especificado no problema
limiteEsquerdo += 2;
limiteDireito += 2;
somaPrefixosA[0] = 0; // Inicializa a soma de prefixo na posição 0
// Lê os elementos de 'arrayA' e calcula as somas de prefixo
for (int i = 1; i <= tamA + 1; i++) {
scanf("%lld", &arrayA[i]);
somaPrefixosA[i] = (somaPrefixosA[i - 1] + arrayA[i]) % MODULO_BASE;
}
// Lê os elementos de 'arrayB'
for (int i = 1; i <= tamB + 1; i++) {
scanf("%lld", &arrayB[i]);
}
long long resultadoFinal = 0; // Variável para armazenar a soma total
// Calcula a contribuição de cada elemento de 'arrayB'
for (int i = 1; i <= tamB + 1; i++) {
// Determina os limites válidos para o subsegmento de 'arrayA'
// O intervalo é [limiteEsquerdo - i, limiteDireito - i]
int l = std::max(1, limiteEsquerdo - i);
int r = std::min(tamA + 1, limiteDireito - i);
// Se o intervalo é inválido (l > r), não há contribuição
if (l > tamA + 1 || r < 1 || l > r) continue;
// Calcula a soma do subsegmento [l, r] de 'arrayA'
long long somaSubsegmentoA = (somaPrefixosA[r] - somaPrefixosA[l - 1] + MODULO_BASE) % MODULO_BASE;
// Adiciona a contribuição de b[i] ao resultado final
resultadoFinal = (resultadoFinal + (arrayB[i] * somaSubsegmentoA) % MODULO_BASE) % MODULO_BASE;
}
printf("%lld\n", resultadoFinal);
}
return 0;
}