Submission #757292

#	Time	Username	Problem	Language	Result	Execution time	Memory
757292		Ozy	Two Currencies (JOI23_currencies)	C++17	100 / 100	3251 ms	171576 KiB

currencies

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define lli long long int
#define pll pair<lli,lli>

#define MAX 100000
#define lg 20
//para el vector de orden
#define val first
#define nodo second
//para los c1
#define ss first
#define cc second

struct x{
    lli hizq;
    lli hder;
    lli sum;
    lli cant;
};

lli n,m,q,a,b,cont,offset,lastkey,gld,sil,ultpos;
lli anc[MAX+2][lg+2];
vector<lli> hijos[MAX+2],plat;
vector<pll> aristas,orden;
vector<x> stree;
map<lli,lli> raiz;
pll euler[MAX+2];
pll c1,c2,c3,best;

void trip(lli pos, lli padre) {

    anc[pos][0] = padre;
    lli movil = padre;
    rep(i,1,lg) {
        anc[pos][i] = anc[movil][i-1];
        movil = anc[pos][i];
    }

    euler[pos].first = cont++;
    for (auto h : hijos[pos]) {
        if (h == padre) continue;
        trip(h,pos);
    }
    euler[pos].second = cont;
}

void update(lli pos, lli ini , lli fin, lli des, lli v) {

    if (ini == fin && ini == des) {
        if (v > 0) {stree[pos].cant++; stree[pos].sum += v;}
        else {stree[pos].cant--; stree[pos].sum += v;}

        /*debugsl(pos);
        debugsl(ini);
        debugsl(fin);
        debug(des);
        debugsl(stree[pos].cant);
        debug(stree[pos].sum);*/

        return;
    }

    lli mitad = (ini + fin)/2;

    if (des <= mitad) {
        stree.push_back( stree[stree[pos].hizq] );
        stree[pos].hizq = cont;
        cont++;
        update(stree[pos].hizq, ini, mitad, des, v);
    }
    else {
        stree.push_back( stree[stree[pos].hder] );
        stree[pos].hder = cont;
        cont++;
        update(stree[pos].hder, mitad+1, fin, des, v);
    }

    stree[pos].sum = stree[ stree[pos].hizq ].sum + stree[ stree[pos].hder ].sum;
    stree[pos].cant = stree[ stree[pos].hizq ].cant + stree[ stree[pos].hder ].cant;

    /*debugsl(pos);
    debugsl(ini);
    debugsl(fin);
    debug(des);
    debugsl(stree[pos].cant);
    debug(stree[pos].sum);*/

}

lli lca(lli a, lli b) {
    lli movil,r = a;

    repa(i,lg,0){
        movil = anc[r][i];
        if (movil == 0) continue;
        if(euler[movil].first <= min(euler[a].first,euler[b].first) && euler[movil].second >= max(euler[a].second,euler[b].second)) continue;

        r = movil;
    }

    if(euler[r].first <= min(euler[a].first,euler[b].first) && euler[r].second >= max(euler[a].second,euler[b].second)) return r;
    else return anc[r][0];
}

pll query(lli pos, lli ini, lli fin, lli l, lli r) {

    if (ini > r || fin < l) return {0,0};
    if (l <= ini && fin <= r) return {stree[pos].sum,stree[pos].cant};

    lli mitad = (ini+fin)/2;
    pll a = query(stree[pos].hizq, ini, mitad, l, r);
    pll b = query(stree[pos].hder, mitad+1, fin, l, r);
    a.ss += b.ss;
    a.cc += b.cc;
    return a;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> q;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
        aristas.push_back({a,b});
    }

    cont = 1;
    trip(1,0);

    rep(i,1,m) {
        cin >> a >> b;
        if (euler[ aristas[a-1].first ].first < euler[ aristas[a-1].second ].first) a = aristas[a-1].second;
        else a = aristas[a-1].first;
        orden.push_back({b,a});
        plat.push_back(b);
    }
    sort(orden.begin(), orden.end());
    sort(plat.begin(), plat.end());
    //correcto

    //debug("LLEGUE");

    //arma el arbol persistente
    cont = 1;
    stree.push_back({0,0,0,0});
    lastkey = 0;
    for(auto act : orden) {

        //debug("nuevo");

        stree.push_back(stree[lastkey]);
        cont++;

        raiz[act.val] = cont-1;
        lastkey = cont-1;
        update(cont-1, 1,n+1, euler[act.nodo].first, act.val);

        //debug(stree[lastkey].cant);
        //debug(stree[lastkey].cant);
        //debug("resta");

        stree.push_back(stree[lastkey]);
        cont++;

        raiz[act.val] = cont-1;
        lastkey = cont-1;
        update(cont-1, 1,n+1, euler[act.nodo].second, -act.val);
    }

    //resuelve
    rep(Q, 1 , q) {
        cin >> a >> b >> gld >> sil;

        //debug("nuevo");

        lli mitad,k,ini = 1;
        lli fin = m;
        ultpos = 0;
        best = {0,0};

        while(ini <= fin) {

            mitad = (ini + fin)/2;
            k = raiz[ plat[mitad-1] ];

            c1 = query(k,1,n+1,1,euler[a].first);
            c2 = query(k,1,n+1,1,euler[b].first);
            c3 = query(k,1,n+1,1,euler[lca(a,b)].first);

            c1.first += c2.first - 2*c3.first;
            c1.second += c2.second - 2*c3.second;

            if (c1.ss <= sil) {
                ultpos = mitad;
                best = c1;
                ini = mitad+1;
            }
            else fin = mitad-1;
        }

        if (ultpos < m) {
            ultpos = plat[ultpos];
            ultpos = (sil - best.ss)/ultpos;
            best.cc += ultpos;
        }

        c1 = query(lastkey,1,n+1,1,euler[a].first);
        c2 = query(lastkey,1,n+1,1,euler[b].first);
        c3 = query(lastkey,1,n+1,1,euler[lca(a,b)].first);

        c1.first += c2.first - 2*c3.first;
        c1.second += c2.second - 2*c3.second;

        k = c1.cc - best.cc;
        gld -= k;

        if (gld >= 0) cout << gld << "\n";
        else cout << -1 << "\n";
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32