El problema presenta un anillo con estaciones fronterizas. Cada soldado teine un intervalo de patrullaje en el anillo. Se busca determinar, para cada soldado, el número mínimo de soldados necesarios para cubrir todo el anillo si ese soldado es el primero en patrullar.

Una técnica común para problemas en anillo es duplicar la línea. Al leer los datos, se añade una copia de cada intervalo desplazada por la longitud total del anillo (m).

struct Warrior {
    int id, left, right;
} w[400005];

cin >> n >> m;
for (int i = 1; i <= n; i++) {
    cin >> w[i].left >> w[i].right;
    if (w[i].right < w[i].left) {
        w[i].right += m;
    }
    w[i].id = i;
}
sort(w + 1, w + n + 1, [](Warrior a, Warrior b) { return a.left < b.left; });
for (int i = 1; i <= n; i++) {
    w[i + n] = w[i];
    w[i + n].left = w[i].left + m;
    w[i + n].right = w[i].right + m;
}

El ordenamiento por left es posible porque los intervalos no se contienen completamente entre sí. Esto garantiza una secuencia monótona.

Para cada guerrero, necesitamos encontrar el guerrero más lejano que pueda alcanzar. La idea es usar binaria lifting (doubling) para acelerar la búsqueda.

Definimos next[i][k] como el guerrero al que se llega después de 2^k saltos comenzando desde el guerrero i.

La tarnsición es:

next[i][k] = next[ next[i][k-1] ][k-1]

Para precalcular el primer salto (next[i][0]), iteramos con un puntero p que se mueve mientras w[p].left <= w[i].right. Al final, next[i][0] = p - 1.

void precompute() {
    int p = 1;
    for (int i = 1; i <= 2 * n; i++) {
        while (p <= 2 * n && w[p].left <= w[i].right) {
            p++;
        }
        next[i][0] = p - 1;
    }
    for (int k = 1; k < 20; k++) {
        for (int i = 1; i <= 2 * n; i++) {
            next[i][k] = next[ next[i][k-1] ][k-1];
        }
    }
}

El límite de 20 (2^20 ≈ 10^6) es suficiente para los casos de prueba.

La función de consulta para un guerrero k (índice en el arreglo duplicado) es:

void query(int start) {
    int limit = w[start].left + m;
    int count = 1;
    int current = start;
    for (int i = 19; i >= 0; i--) {
        if (next[current][i] != 0 && w[ next[current][i] ].right < limit) {
            count += (1 << i);
            current = next[current][i];
        }
    }
    answer[ w[start].id ] = count + 1;
}

El resultado se almacena en el arreglo answer indexado por id original.

El código completo:

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
const int LOG = 20;

struct Warrior {
    int id, left, right;
} w[MAXN * 2];

int n, m;
int answer[MAXN];
int nextTable[MAXN * 2][LOG];

void precompute() {
    int p = 1;
    for (int i = 1; i <= 2 * n; i++) {
        while (p <= 2 * n && w[p].left <= w[i].right) {
            p++;
        }
        nextTable[i][0] = p - 1;
    }
    for (int k = 1; k < LOG; k++) {
        for (int i = 1; i <= 2 * n; i++) {
            nextTable[i][k] = nextTable[ nextTable[i][k-1] ][k-1];
        }
    }
}

void query(int start) {
    int limit = w[start].left + m;
    int count = 1;
    int cur = start;
    for (int i = LOG - 1; i >= 0; i--) {
        int nxt = nextTable[cur][i];
        if (nxt != 0 && w[nxt].right < limit) {
            count += (1 << i);
            cur = nxt;
        }
    }
    answer[ w[start].id ] = count + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i].left >> w[i].right;
        if (w[i].right < w[i].left) {
            w[i].right += m;
        }
        w[i].id = i;
    }
    sort(w + 1, w + n + 1, [](Warrior a, Warrior b) { return a.left < b.left; });
    for (int i = 1; i <= n; i++) {
        w[i + n] = w[i];
        w[i + n].left = w[i].left + m;
        w[i + n].right = w[i].right + m;
    }
    precompute();
    for (int i = 1; i <= n; i++) {
        query(i);
    }
    for (int i = 1; i <= n; i++) {
        cout << answer[i] << " ";
    }
    cout << endl;
    return 0;
}