A - Problema do Tapete

Este problema utiliza a técnica de soma de prefixos com diferenças em duas dimensões. Definimos \(s_{i,j}\) como o valor da célula atual e simulamos a operação descrita no enunciado usando diferenças e somas prefixas.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 10, mod = 1e9 + 7;
int grade[N][N];
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int dimensao, operacoes; cin >> dimensao >> operacoes;
    for(int i = 1; i <= operacoes; i++){
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        grade[x1][y1] ++, grade[x1][y2 + 1] --, grade[x2 + 1][y1] --, grade[x2 + 1][y2 + 1] ++;
    }
    for(int i = 1; i <= dimensao; i++){
        for(int j = 1; j <= dimensao; j++){
            grade[i][j] = grade[i][j] + grade[i - 1][j] + grade[i][j - 1] - grade[i - 1][j - 1];
            cout << grade[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

B - Árvore FBI

Simulando o enunciado do problema, primeiro ajustamos o número de nós para o comprimento adequado \(2^n\). Realizamos duas travessias em profundidade (dfs). A primeira é similar a uma árvore de segmentos, armazenando informações dos nós e intervalos. Note que mesmo se os dois filhos forem iguais, o valor pode ser 'F' se um deles for 'F'. Na segunda dfs, verificamos primeiro os nós folha, depois os filhos esquerdo e direito, e finalmente o nó raiz.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
struct no{
    int esquerda, direita;
    char valor;
};
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    n = 1 << n;
    string sequencia; cin >> sequencia;
    sequencia = " " + sequencia;
    vector<no> arvore(n * 4 + 1);
    function<void(int, int, int)> dfs1;
    dfs1 = [&](int u, int l, int r) -> void{
        if(l == r){
            if(sequencia[l] == '1') arvore[u] = {l, r, 'I'};
            else if(sequencia[l] == '0') arvore[u] = {l, r, 'B'};
            else arvore[u] = {l, r, 'F'};
            return;
        }
        arvore[u] = {l, r};
        int meio = l + r >> 1;
        dfs1(u << 1, l, meio), dfs1(u << 1 | 1, meio + 1, r);
        if(arvore[u << 1].valor == arvore[u << 1 | 1].valor){
            if(arvore[u << 1].valor == 'I') arvore[u].valor = 'I';
            else if(arvore[u << 1].valor == 'B') arvore[u].valor = 'B';
            else arvore[u].valor = 'F';
        }
        else arvore[u].valor = 'F';
    };
    function<void(int)> dfs2;
    dfs2 = [&](int u) -> void{
        if(arvore[u].esquerda == arvore[u].direita){
            cout << arvore[u].valor;
            return;
        }
        dfs2(u << 1), dfs2(u << 1 | 1);
        cout << arvore[u].valor; 
    };
    dfs1(1, 1, n);
    dfs2(1);
    return 0;
}

C - Problema das Vacas

Cada vaca olha para a primeira vaca à sua direita que é mais alta que ela. Isso é equivalente a encontrar o primeiro número crescente ao olhar da esquerda para a direita. Podemos usar uma pilha monotônica, processando da direita para a esquerda com uma pilha crescente. A pilha armazena os índices das vacas em ordem crescente de altura, funcionando como uma ponte. Se a vaca atual for mais alta que o topo da pilha, removemos o topo. Se a pilha estiver vazia, não há vaca mais alta à direita. Caso contrário, a vaca no topo da pilha é a primeira mais alta à direita, e então adicionamos a vaca atual à pilha.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10, mod = 1e9 + 7;
signed main()
{
    int n; cin >> n;
    vector<int> altura(n + 1);
    for(int i = 1; i <= n; i++) cin >> altura[i];
    stack<int> pilha;
    vector<int> resultado(n + 1);
    for(int i = n; i >= 1; i--){
        while(!pilha.empty() && altura[i] >= altura[pilha.top()]) pilha.pop();
        if(pilha.empty()) resultado[i] = 0;
        else resultado[i] = pilha.top();
        pilha.push(i);
    }
    for(int i = 1; i <= n; i++) cout << resultado[i] << '\n';
    return 0;
}

D - Minimizando a Diferença

Consideramos uma abordagem gulosa. Primeiro, ordenamos o array, pois isso facilita encontrar os valores extremos. Para minimizar a diferença entre o máximo e o mínimo, removemos elementos das duas extremidades. O que resta é um intervalo contínuo. Podemos enumerar esse intervalo. Se estivermos na posição \(i\), a posição final é \(i + n - k - 1\). Precisamos encontrar:

[\min_{1 \le i \le N, i + N - K - 1 \le N} (A_{i + N - K - 1} - A_{i}) ]

Calculamos diretamente, com complexidade de tempo \(O(n \log n)\).

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    vector<int> valores(n + 1);
    for(int i = 1; i <= n; i++) cin >> valores[i];
    sort(valores.begin() + 1, valores.end());
    if(k >= valores.size()) return cout << 0 << '\n', 0;
    int resposta = 1e10;
    for(int i = 1; i <= k + 1; i++){
        resposta = min(resposta, valores[i + n - k - 1] - valores[i]);
    }
    cout << resposta << '\n';
    return 0;
}

E - Custo de Percursos em Cidades

Analisando caminhos adjacentes, podemos细分 \(a ➡ b\) as cidades percorridas. Como as cidades são fixas, usamos somas prefixas para resolver o problema. Para cada caminho, calculamos o custo entre cidades adjacentes. Usamos duas somas prefixas: uma para a direção esquerda-direita (\(soma1\)) e outra para direita-esquerda (\(soma2\)).

• Se a distância entre cidades adjacentes atender à primeira condição, o custo é \(1\)
• Caso contrário, o custo é \(|a_{i + 1} - a_i|\)

Por exemplo, para o caminho \(2 ➡ 4\), consideramos \(2 ➡ 3\) e depois \(3 ➡ 4\), usando uma abordagem gulosa para obter a solução ótima.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+10, mod = 1e9 + 7;
void resolver(){
    int n; cin >> n;
    vector<int> cidades(n + 10), soma1(n + 10, 0), soma2(n + 10, 0);
    for(int i = 1; i <= n; i++) cin >> cidades[i];
    cidades[0] = cidades[1], cidades[n + 1] = 1e9;
    for(int i = 1; i < n; i++){
        if(i == 1){
            soma1[i] = 1;
            continue;
        }
        if(abs(cidades[i] - cidades[i + 1]) < abs(cidades[i] - cidades[i - 1])) soma1[i] = soma1[i - 1] + 1;
        else soma1[i] = soma1[i-1] + abs(cidades[i] - cidades[i + 1]);
    }
    for(int i = n; i > 1; i--){
        if(i == n){
            soma2[i] = 1;
            continue;
        }
        if(abs(cidades[i] - cidades[i - 1]) < abs(cidades[i] - cidades[i + 1])) soma2[i] = soma2[i + 1] + 1;
        else soma2[i] = soma2[i + 1] + abs(cidades[i - 1] - cidades[i]);
    }
    int m; cin >> m;
    while(m--){
        int a, b; cin >> a >> b;
        if(a < b) cout << soma1[b - 1] - soma1[a - 1] << '\n';
        else if(a > b) cout << soma2[b + 1] - soma2[a + 1] << '\n';
        else cout << '0' << '\n';
    }
    
}
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;cin>>t;while(t--)resolver();
}

F - Encontro de Trabalhdaores

Método de Ordenação Mesclada (Merge Sort)

A maioria das soluções usa busca binária e ponteiros duplos. Aqui apresentamos uma solução usando pares de inversão. Como cada trabalhador tem uma direção fixa e não muda, após percorrer o caminho, se um trabalhador com número menor chegar atrás de um com número maior, eles certamente se encontrarão. Podemos usar pares de inversão.

Importante:

• As coordenadas dos trabalhadores não estão necessariamente em ordem crescente, como pode enganar nos exemplos. Devemos primeiro ordená-las.
• Para coordenadas iguais, ordenamos por número decrescente de identificação para facilitar a contagem.

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
struct trabalhador{
    int pos, id, direcao;
    bool operator<(const trabalhador &w) const{
        if(pos == w.pos) return id > w.id;
        else return pos < w.pos;
    }
}a[N];
int temp[N], inversoes;
bool cmp(trabalhador a, trabalhador b){
    return a.pos < b.pos;
}
void merge_sort(int l, int r){
    if(l == r) return;
    int mid = l + r >> 1, i = l, j = mid + 1, num = l;
    merge_sort(l, mid), merge_sort(mid + 1, r);
    while(i <= mid && j <= r){
        if(a[i].id <= a[j].id) temp[num++] = a[i++].id;
        else inversoes += mid - i + 1, temp[num++] = a[j++].id;
    }
    while(i <= mid) temp[num++] = a[i++].id;
    while(j <= r) temp[num++] = a[j++].id;
    for(int i = l; i <= r; i++) a[i].id = temp[i];
}
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, tempo; cin >> n >> tempo;
    string direcoes; cin >> direcoes;
    direcoes = " " + direcoes;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        a[i] = {x, i, direcoes[i] - '0'};  
    }
    sort(a + 1, a + 1 + n, cmp);
    for(int i = 1; i <= n; i++){
        a[i].id = i;
        if(a[i].direcao == 1) a[i].pos += tempo;
        else a[i].pos -= tempo;
    }
    sort(a + 1, a + 1 + n);
    merge_sort(1, n);
    cout << inversoes << '\n';
    return 0;
}

Método de Busca Binária ou Ponteiros Duplos

Ordenamos as formigas. Sabemos que dois trabalhadores na mesma direção não podem se encontrar. Portanto, dividimos os trabalhadores em dois grupos: um indo para a esquerda e outro para a direita.

• Para um trabalhador indo para a esquerda com identificação \(x\), para encontrar um trabalhador indo para a direita com quem ele se encontre, a diferença entre suas posições deve ser menor que \(2 * tempo\). Portanto, fazemos uma busca binária por um trabalhador indo para a direita com identificação \(y\) tal que sua posição seja menor ou igual à posição do trabalhador \(x\) + \(2 * tempo\). Nessa faixa \(x\) ~ \(y\), todos os trabalhadores se encontrarão com ele, ou seja, \(y - x\) trabalhadores.
• Usando dois ponteiros \(l = r = 1\), enumeramos a identificação do trabalhador indo para a direita \(i\). Se o trabalhador indo para a esquerda com identificação \(l\) tem\(x_i > x_l\), incrementamos até \(x_l > x_i\). Da mesma forma para \(r\), queremos que não ultrapasse \(x_r - x_i <= 2 * tempo\). A resposta para o trabalhador atual \(i\) é \(r - l\).

G - Maximizando o Produto

Este problema parece complexo inicialmente. Embora a programação dinâmica seja uma abordagem óbvia, a equação resultante é difícil de manter:

[dp_i = dp_j + dp2_j * s(i, j) ]ou

[dp_i = min(a_i...a_j) * s(a_i...a_j) ]É difícil manter o mínimo e a soma do intervalo. Portanto, consideramos se uma abordagem gulosa é viável. Podemos enumerar o valor mínimo, o que nos dá \(O(n)\) enumerações. Definimos uma estrutura para manter informações: valor \(val\) e posição \(id\).

Considerando que a resposta composta por um valor mínimo é fixa, ou seja, expandindo para a esquerda e direita a partir do mínimo até encontrar um valor menor, esse intervalo é a contribuição máxima que podemos obter com esse mínimo. Isso está correto porque não existe um maior intervalo com esse número como mínimo.

Ordenamos em ordem crescente, marcamos cada número enumerado e paramos a expansão quando encontramos um marcado. Como marcamos \(n\) elementos, a complexidade é \(O(nlogn + n)\). Como os valores não excedem \(10^6\), podemos usar ordenação por bucket para otimizar para \(O(n + n)\).

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
struct elemento{
    int valor, posicao;
    bool operator<(const elemento &w) const{
        return valor < w.valor;
    }
}a[N];
int soma[N];
bool visitado[N];
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        int x; cin >> x; 
        a[i] = {x, i};
        soma[i] = soma[i - 1] + a[i].valor;
    }
    sort(a + 1, a + 1 + n);
    int resposta = a[1].valor * soma[n];
    visitado[0] = true, visitado[a[1].posicao] = true;
    for(int i = 2; i <= n; i++){
        int l = a[i].posicao, r = a[i].posicao;
        while(l && !visitado[l - 1]) l --;
        while(r < n && !visitado[r + 1]) r ++;
        resposta = max(resposta, a[i].valor * (soma[r] - soma[l - 1]));
        visitado[a[i].posicao] = true;
    }
    cout << resposta << '\n';
    return 0;
}

H - Dividindo o Bolo

Derivando a equação, seja \(dp_i\) a contribuição máxima na posição \(i\) e \(s_i\) a soma prefixa, temos:

[dp_i = max(s_i - s_j)|j∈[i - m, i - 1] ]Notamos que \(s_i\) é independente de \(j\), então podemos fatorá-lo:

[dp_i = s_i - min(s_{j_1}, s_{j_2}, s_{j_3}....s_{j}) | j∈[i - m, i - 1] ]Portanto, precisamos manter o valor mínimo estático em um intervalo de somas prefixas, o que pode ser feito com árvore de segmentos, tabela ST, árvore de Fenwick ou fila monotônica. Aqui usamos uma fila monotônica:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    vector<int> valores(n + 1), soma(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> valores[i];
        soma[i] = soma[i - 1] + valores[i];
    }
    vector<int> fila(n + 1), dp(n + 1);
    int inicio = 0, fim = -1;
    for(int i = 0; i <= n; i++){
        while(inicio <= fim && fila[inicio] + m < i) inicio ++;
        while(inicio <= fim && soma[i] <= soma[fila[fim]]) fim --;
        fila[++fim] = i, dp[i] = fila[inicio];
    }
    int resultado = 0;
    for(int i = 1; i <= n; i++){
        resultado = max(resultado, soma[i] - soma[dp[i]]);
    }
    cout << resultado << '\n';
    return 0;
}