← voltar para a publicação›Editar / bifurcar

Publicação sem título

#4pCPFuegpKpublic / publicnova versão

anônimo criado 51 minutes ago Expira em 7 days 2.8 KB sintaxe: cpp

Suas alterações criam uma nova publicação vinculada a esta — a original não é alterada.

nova versão Suas alterações criam uma nova publicação vinculada a esta — a original não é alterada.

Visibilidade Feed público Acesso public

Nota da alteração (opcional)

Esta publicação aparecerá no feed público. Altere Visibilidade se quiser compartilhar apenas por link.

Cancelar

#include <bits/stdc++.h>

using i64 = long long;

void Solve() {
    int n;
    i64 d;
    std::cin >> n >> d;

std::vector<i64> x(n);
    for (int i = 0; i < n; i++) {
        std::cin >> x[i];
    }

std::vector<int> right(n, -1);

for (int i = n - 1, j = n - 1; i >= 0; i--) {
        while (j > i && x[j] - x[i] > d) {
            j--;
        }
        right[i] = j;
    }

std::vector<int> g(n, n);
    std::vector<int> left(n, n);

for (int i = 0, j = 0; i < n; i++) {
        while (j < i && x[i] - x[j] > d) {
            j++;
        }
        
        g[j] = std::min(g[j], i);
        left[i] = j;
    }

constexpr int A = 3, B = 3, V = 2;
    constexpr int STRIDE_A = B * V;        // 6
    constexpr int STRIDE_B = V;            // 2
    constexpr int STRIDE_I = A * B * V;    // 18

std::vector<int> f(n * STRIDE_I);
    auto F = [&](int i, int a, int b, int v) -> int& {
        return f[i * STRIDE_I + (a - 1) * STRIDE_A + (b - 1) * STRIDE_B + (v - 1)];
    };

for (int i = n - 1; i >= 1; i--) {
        if (right[i] == i) {
            continue;
        }

int j = right[i];

if (j == i) {
            continue;
        }

for (int a = 1; a <= 3; a++) {
            for (int b = 1; b <= 3; b++) {
                if (j == i + 1) {
                    int c = std::min(3, left[j] == i ? b : left[j] == i - 1 ? a + b : 3);
                    F(i, a, b, 1) += F(j, 1, c, 1); 
                    F(i, a, b, 2) += F(j, 1, c, 2);

if (c <= 2) {
                        F(i, a, b, c) += 1;
                    }

continue;
                }

int p1 = std::max(i + 1, g[i - 1]), p2 = std::min(j + 1, g[i]);
                    
                if (b <= 2) {
                    F(i, a, b, b) += j - p2 + 1;
                }
                
                if (a + b <= 2) {
                    F(i, a, b, a + b) += std::max(0, p2 - p1);
                }

int c = std::min(3, left[j - 1] < i - 1 ? 3 : left[j - 1] == i - 1 ? a + b : b);
                int d = std::min(3, left[j] < i - 1 ? 3 : left[j] == i - 1 ? a + b : b);

F(i, a, b, 1) += F(j, c, d, 1);
                F(i, a, b, 2) += F(j, c, d, 2);
            }
        }
    }

i64 ans = 0, lst = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (right[i] == i) {
            lst = 0;
            continue;
        }

if (right[i] == i + 1) {
            ans += lst;
            continue;
        }

lst = F(right[i], 1, 1, 2);
        ans += lst;

// std::cout << lst << " ";
    }
   // std::cout << "\n";

std::cout << ans << '\n';
 }

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

int c, t;
    std::cin >> c >> t;

while (t --) {
        Solve();
    }

return 0;
}