Submission #1154409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154409		Pichon5	새로운 문제 (POI11_met)	C++20	100 / 100	1018 ms	44920 KiB

met

#include <bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
using namespace std;
 
const int tam = 300030;
const ll INF = 1e16;
 
unsigned long long T[2 * tam];
ll n, m, k;
vector<vll> G;
ll E[tam];
ll res[tam];
 
// Las queries (updates) se almacenan como: 
// Q[i] = { {l, r}, val } 
// (donde se debe aplicar update en BIT: update(l, val); update(r+1, -val); 
//  (además, si r < l se “envuelve” el intervalo)
vector<pair<pair<ll, ll>, ll>> Q;
 
// BIT (Fenwick Tree)
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;
}
 
int main(){
    fast;
    ll x;
    cin >> n >> m;
    // G: para cada nodo (1-indexado) se guardan posiciones (1..m)
    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});
    }
    
    // Para cada nodo (consulta) definimos los límites de búsqueda.
    // L[i] y R[i] son los índices en el arreglo de updates (Q), y la respuesta se guarda en ans[i]
    vector<ll> L(n + 1, 0), R(n + 1, k - 1), ans(n + 1, k + 1);
    
    bool updated = true;
    // Mientras alguna consulta no esté resuelta (L[i] <= R[i])
    while(updated){
        updated = false;
        // buckets[j] contendrá los nodos cuya búsqueda actual tiene mid = j.
        vector<vll> buckets(k);
        for (int i = 1; i <= n; i++){
            if(L[i] <= R[i]){
                updated = true;
                ll mid = (L[i] + R[i]) / 2;
                buckets[mid].pb(i);
            }
        }
        // Reiniciamos BIT (T) a cero
        memset(T, 0, sizeof(T));
        // Se “aplican” los updates en orden (de 0 a k-1)
        for (int j = 0; j < k; j++){
            ll l = Q[j].F.F, r = Q[j].F.S, val = Q[j].S;
            update(l, val);
            // Si el intervalo se “envuelve”
            if(r < l){
                update(1, val);
                update(m + 1, -val);
            }
            update(r + 1, -val);
            
            // Para cada nodo asignado a este candidato medio (j)
            for (ll node : buckets[j]){
                ll sum = 0;
                // Sumar las contribuciones en todas las posiciones indicadas en G[node]
                for (auto pos : G[node]){
                    sum += query(pos);
                    if(sum >= 1e10) break; // corte temprano si la suma es grande
                }
                if(sum >= E[node]){
                    // Se cumple la condición, se puede intentar mejorar la respuesta
                    ans[node] = min(ans[node], (ll)j + 1);
                    R[node] = j - 1;
                } else {
                    L[node] = j + 1;
                }
            }
        }
    }
    
    // Se imprime la respuesta para cada nodo (consulta)
    for (int i = 1; i <= n; i++){
        if(ans[i] == k + 1)
            cout << "NIE" << "\n";
        else
            cout << ans[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