Submission #875460

#	Time	Username	Problem	Language	Result	Execution time	Memory
875460		andrei_iorgulescu	Two Currencies (JOI23_currencies)	C++14	100 / 100	2504 ms	76408 KiB

currencies

#include <bits/stdc++.h>

using namespace std;

ifstream in("f.in");
ofstream out("f.out");

#define int long long

int bucket_size = 700;

int n,m,q,N;
vector<int>G[100005];
vector<pair<int,int>>g[200005];
pair<int,int>edges[100005];
vector<int>midedges[100005];

struct ura
{
    int nrgold,nrsilver,x,y,idx;
};

bool cmp(ura A,ura B)
{
    if (A.x / bucket_size != B.x / bucket_size)
        return A.x < B.x;
    return A.y < B.y;
}

ura v[100005];
int curpm;
pair<int,int> pm[400005];
bool viz[200005];
int valoare[200005];
int tin[200005],tout[200005];
int height[200005];
int tata[200005];
int rval[300005];
int raspuns[100005];

void traversal(int nod)
{
    viz[nod] = true;
    pm[++curpm] = {nod,valoare[nod]};
    tin[nod] = curpm;
    for (auto vecin : g[nod])
        if (!viz[vecin.first])
        {
            height[vecin.first] = 1 + height[nod];
            tata[vecin.first] = nod;
            valoare[vecin.first] = vecin.second;
            traversal(vecin.first);
        }
    pm[++curpm] = {nod,valoare[nod]};
    tout[nod] = curpm;
}

int lmo = 1,rmo = 0;

bool am[200005];
int fr[300005],sm[300005];
int frb[505],smb[505];
int catetot;

void normalize_values()
{
    map<int,int>mpnorma;
    int posnorma = 0;
    vector<int>vnorma;
    for (int i = 1; i <= n; i++)
        vnorma.push_back(valoare[i]);
    sort(vnorma.begin(),vnorma.end());
    for (int i = 0; i < vnorma.size(); i++)
        if (!mpnorma[vnorma[i]])
            mpnorma[vnorma[i]] = ++posnorma,rval[posnorma] = vnorma[i];
    for (int i = posnorma + 1; i <= 300000; i++)
        rval[i] = 2e18,fr[i] = 1,sm[i] = 2e18,frb[i / bucket_size]++,smb[i / bucket_size] = 2e18;
    for (int i = 1; i <= n; i++)
        valoare[i] = mpnorma[valoare[i]];
    for (int i = 1; i <= 2 * n; i++)
        pm[i].second = valoare[pm[i].first];
}

void upd(int x,int coef)
{
    //out << pm[x].first << ' ' << coef << '\n';
    catetot += coef;
    int vl = pm[x].second,rvl = rval[vl];
    fr[vl] += coef;
    sm[vl] += coef * rvl;
    frb[vl / bucket_size] += coef;
    smb[vl / bucket_size] += coef * rvl;
}

void baga(int x,int coef)
{
    //cout << x << ' ' << coef << '\n';
    if ((am[pm[x].first] == false and coef == 1) or (am[pm[x].first] == true and coef == -1))
    {
        upd(x,coef);
    }
    else
    {
        upd(x,-coef);
    }
    if (am[pm[x].first] == true)
        am[pm[x].first] = false;
    else
        am[pm[x].first] = true;
}

void ansquery(int pos)
{
    int gold = v[pos].nrgold,silver = v[pos].nrsilver;
    int catenice = 0;
    for (int i = 0; i <= n / bucket_size; i++)
    {
        if (silver == 0)
        {
            if (i == 0)
            {
                catenice += fr[1];
            }
            break;
        }
        if (silver >= smb[i])
        {
            silver -= smb[i];
            catenice += frb[i];
        }
        else
        {
            for (int j = i * bucket_size; j < (i + 1) * bucket_size; j++)
            {
                if (silver >= sm[j])
                {
                    silver -= sm[j];
                    catenice += fr[j];
                }
                else
                {
                    catenice += silver / rval[j];
                    silver = 0;
                }
            }
        }
    }
    gold -= (catetot - catenice);
    if (gold < 0)
        raspuns[v[pos].idx] = -1;
    else
        raspuns[v[pos].idx] = gold;
}

void mo()
{
    for (int i = 1; i <= q; i++)
    {
        while (rmo < v[i].y)
        {
            rmo++;
            baga(rmo,1);
        }
        while (lmo > v[i].x)
        {
            lmo--;
            baga(lmo,1);
        }
        while (rmo > v[i].y)
        {
            baga(rmo,-1);
            rmo--;
        }
        while (lmo < v[i].x)
        {
            baga(lmo,-1);
            lmo++;
        }
        ansquery(i);
    }
}

void buildg()
{
    n = N + m;
    int cur = N;
    for (int i = 1; i < N; i++)
    {
        int x = edges[i].first,y = edges[i].second;
        if (midedges[i].size() == 0)
        {
            g[x].push_back({y,0});
            g[y].push_back({x,0});
        }
        else
        {
            cur++;
            g[x].push_back({cur,midedges[i][0]});
            g[cur].push_back({x,midedges[i][0]});
            for (int j = 1; j < midedges[i].size(); j++)
            {
                cur++;
                g[cur - 1].push_back({cur,midedges[i][j]});
                g[cur].push_back({cur - 1,midedges[i][j]});
            }
            g[cur].push_back({y,0});
            g[y].push_back({cur,0});
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> m >> q;
    for (int i = 1; i < N; i++)
    {
        int x,y;
        cin >> x >> y;
        if (x > y)
            swap(x,y);
        G[x].push_back(y);
        G[y].push_back(x);
        edges[i] = {x,y};
    }
    for (int i = 1; i <= m; i++)
    {
        int p,c;
        cin >> p >> c;
        midedges[p].push_back(c);
    }
    buildg();
    /*for (int i = 1; i <= n; i++)
    {
        out << g[i].size() << '\n';
        for (int j = 0; j < g[i].size(); j++)
            out << g[i][j].first << ' ' << g[i][j].second << '\n';
    }*/
    for (int i = 1; i <= q; i++)
        cin >> v[i].x >> v[i].y >> v[i].nrgold >> v[i].nrsilver,v[i].idx = i;
    traversal(1);
    /*for (int i = 1; i <= 2 * n; i++)
    {
        out << pm[i].first << ' ' << pm[i].second << '\n';
    }*/
    for (int i = 1; i <= q; i++)
    {
        if (tin[v[i].x] > tin[v[i].y])
            swap(v[i].x,v[i].y);
        if (tout[v[i].x] > tin[v[i].y])
            v[i].x = tin[v[i].x] + 1,v[i].y = tin[v[i].y];
        else
            v[i].x = tout[v[i].x],v[i].y = tin[v[i].y];
    }
    //out << '\n';
    sort(v + 1,v + q + 1,cmp);
    /*for (int i = 1; i <= q; i++)
        out << v[i].x << ' ' << v[i].y << '\n';*/
    normalize_values();
    mo();
    for (int i = 1; i <= q; i++)
        cout << raspuns[i] << '\n';
    return 0;
}

/**
daca am o taxa de c pe muchia x-y, pot crea un nod fictiv pe muchia x y, fie el z, a.i x z e muchia anterioara si z y e o muchie de cost c

bun, acum ca am query-uri pe liniarizare
e ceva de genul: pe interv [x y], cate pot lua cu suma <= z?
cand mut capetele in mo, bag sau scot elemente
3 tipuri de operatii acum:
-baga x
-scoate x
-cate elem pot avea cu suma <= z?

imi tin valorile alea normalizate (ca totusi)
si bag un sqrt decomp frumos
gasesc ultimul bucket din care pot lua tot
din urmatorul merg unul cate unul si iau ce pot
**/

Compilation message (stderr)

currencies.cpp: In function 'void normalize_values()':
currencies.cpp:73:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int i = 0; i < vnorma.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
currencies.cpp: In function 'void buildg()':
currencies.cpp:200:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |             for (int j = 1; j < midedges[i].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~

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