Submission #1154410

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154410		Pichon5	Meteors (POI11_met)	C++20	100 / 100	676 ms	38680 KiB

met

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
 
const int tam = 300030;
const ll INF = 1e16;
 
// BIT (Fenwick Tree)
unsigned long long T[2 * tam];
ll n, m, k;
vector<vll> G; // Para cada nodo (1-indexado) se guardan posiciones (en [1, m])
ll E[tam];     // Para cada nodo se tiene un umbral
ll res[tam];   // Respuesta para cada nodo (mínimo update en el que se cumple la condición)
 
// Las queries (updates) se almacenan en Q:
// Q[i] = { {l, r}, val } indica que se debe aplicar:
//    update(l, val); update(r+1, -val);
// (además, si r < l se “envuelve” el intervalo)
vector<pair<pair<ll,ll>, ll>> Q;
 
void update(int pos, int val) {
    while (pos <= m) {
        T[pos] += val;
        pos += (pos & -pos);
    }
}
 
ll query(ll pos) {
    unsigned long long ans = 0;
    while (pos > 0) {
        ans += T[pos];
        pos -= (pos & -pos);
    }
    return ans;
}
 
// Definimos dos tipos de acción para simular la recursión
enum ActionType { PROCESS, ROLLBACK };
 
// Una acción de la pila contendrá:
// - Para PROCESS: el intervalo de updates [b, e] y la lista de nodos a evaluar.
// - Para ROLLBACK: el intervalo [b, mid] que se usó en un PROCESS para luego deshacer los BIT updates.
struct Action {
    ActionType type;
    ll b, e, mid; // Para PROCESS: se usan b y e; para ROLLBACK: se usan b y mid (e no importa)
    vll nodes;    // Solo para PROCESS.
};
 
// Función iterativa de parallel binary search usando una pila (stack)
void parallel_stack() {
    stack<Action> st;
    // Estado inicial: buscamos en el rango de updates [0, k-1] para todos los nodos (1..n)
    vll allNodes;
    for (int i = 1; i <= n; i++) {
        allNodes.pb(i);
    }
    st.push({PROCESS, 0, k - 1, -1, allNodes});
 
    while (!st.empty()) {
        Action cur = st.top();
        st.pop();
 
        if (cur.type == PROCESS) {
            // Si no hay nodos o el intervalo de updates es inválido, saltamos
            if (cur.nodes.empty() || cur.b > cur.e) continue;
 
            ll mid = (cur.b + cur.e) / 2;
 
            // Aplicamos los BIT updates para los updates en el intervalo [cur.b, mid]
            for (ll i = cur.b; i <= mid; i++) {
                ll l = Q[i].F.F, r = Q[i].F.S, val = Q[i].S;
                update(l, val);
                if (r < l) {
                    update(1, val);
                    update(m + 1, -val);
                }
                update(r + 1, -val);
            }
 
            // Separamos los nodos en dos grupos:
            // A: aquellos que cumplen la condición (suma >= E[node])
            // B: los que no cumplen.
            vll A, B;
            for (ll node : cur.nodes) {
                ll sum = 0;
                for (auto pos : G[node]) {
                    sum += query(pos);
                    if (sum >= 1e10) break; // corte temprano
                }
                if (sum >= E[node]) {
                    A.pb(node);
                    res[node] = min(res[node], mid + 1); // mid es 0-indexado, guardamos mid+1
                } else {
                    B.pb(node);
                }
            }
 
            // Para simular la recursión:
            // Se debe procesar primero el branch derecho (con BIT aún aplicado),
            // luego hacer rollback de los updates, y finalmente procesar el branch izquierdo.
            // Debido a LIFO, empujamos en el orden inverso:
            // 1. Push PROCESS para el branch izquierdo ([cur.b, mid-1], nodos A) si no está vacío.
            // 2. Push ROLLBACK (para deshacer updates en [cur.b, mid]).
            // 3. Push PROCESS para el branch derecho ([mid+1, cur.e], nodos B) si no está vacío.
 
            if (!A.empty() && cur.b <= mid - 1) {
                st.push({PROCESS, cur.b, mid - 1, -1, A});
            }
            st.push({ROLLBACK, cur.b, 0, mid, {}}); // ROLLBACK: guardamos b y mid.
            if (!B.empty() && mid + 1 <= cur.e) {
                st.push({PROCESS, mid + 1, cur.e, -1, B});
            }
 
        } else { // Acción ROLLBACK: deshacemos los BIT updates aplicados en [cur.b, cur.mid]
            for (ll i = cur.b; i <= cur.mid; i++) {
                ll l = Q[i].F.F, r = Q[i].F.S;
                ll val = -Q[i].S; // Inverso del valor aplicado anteriormente
                update(l, val);
                if (r < l) {
                    update(1, val);
                    update(m + 1, -val);
                }
                update(r + 1, -val);
            }
        }
    }
}
 
int main(){
    fast;
    ll x;
    cin >> n >> m;
    // Para cada nodo (1 a n) se guarda una lista de posiciones (índices de update) que le afectan.
    G.assign(n + 1, vll());
    for (int i = 1; i <= m; i++){
        cin >> x;
        G[x].pb(i);
    }
    for (int i = 1; i <= n; i++){
        cin >> E[i];
    }
    cin >> k;
    for (int i = 0; i < k; i++){
        ll l, r, val;
        cin >> l >> r >> val;
        Q.pb({{l, r}, val});
    }
    // Inicializamos res para cada nodo; si no se alcanza, se mantiene k+1
    for (int i = 0; i <= n; i++) {
        res[i] = k + 1;
    }
    // Aseguramos que el BIT esté en cero
    memset(T, 0, sizeof(T));
 
    parallel_stack();
 
    for (int i = 1; i <= n; i++){
        if (res[i] == k + 1)
            cout << "NIE" << "\n";
        else
            cout << res[i] << "\n";
    }
 
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13