Submission #1210278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210278		dima2101	Two Currencies (JOI23_currencies)	C++20	0 / 100	0 ms	324 KiB

currencies

#include <bits/stdc++.h>
#define int long long

struct Node
{
    int start;
    int stop;
    int cost;
    int ind;

    Node(int start, int stop, int cost, int ind) : start(start),
                                                   stop(stop), cost(cost), ind(ind) {};
    Node() = default;
};

struct Query
{
    int l, r;
    int ser;
    int gold;
    int ind;

    Query(int l, int r, int ser, int gold, int ind) : l(l), r(r), ser(ser), gold(gold), ind(ind) {};
    Query() = default;
};

std::vector<int>
    tin;
std::vector<int> order;
int T = 0;
void dfs(int v, std::vector<std::vector<Node>> &g, int pred = -1)
{

    for (auto u : g[v])
    {
        if (u.stop != pred)
        {
            tin[u.stop] = order.size();
            order.push_back(u.ind);
            dfs(u.stop, g, v);
            order.push_back(u.ind);
        }
    }
}

const int LEN = 400;
struct Corn
{
    int n;
    std::vector<int> a;
    std::vector<int> sum;
    std::vector<int> cnt;
    int all;

    Corn(int n) : n(n)
    {
        a.resize(n);
        cnt.resize((n + LEN - 1) / LEN + 2);
        sum.resize(cnt.size());
    }

    void add(int i, int x)
    {
        // std::cout << "add " << i << ' ' << x << std::endl;
        all++;
        a[i] += x;
        sum[i / LEN] += x;
        cnt[i / LEN]++;
    }

    void del(int i)
    {
        // std::cout << "del " << a[i] << std::endl;
        all--;
        sum[i / LEN] -= a[i];
        cnt[i / LEN]--;
        a[i] = 0;
    }

    int need_gold(int ser)
    {
        // for (int i = 0; i < a.size(); i++)
        // {
        //     std::cout << a[i] << ' ';
        // }
        // std::cout << std::endl;
        int cnt1 = 0;
        int ind = -1;
        for (int i = 0; i < sum.size(); i++)
        {
            if (ser < sum[i])
            {
                ind = i;
                break;
            }
            else
            {
                ser -= sum[i];
                cnt1 += cnt[i];
            }
        }
        if (ind == -1)
        {
            return 0;
        }
        for (int j = LEN * ind; j < std::min((int)a.size(), (LEN) * (ind + 1)); j++)
        {
            if (a[j] != 0)
            {
                if (ser >= a[j])
                {
                    ser -= a[j];
                    cnt1++;
                }
                else
                {
                    return all - cnt1;
                }
            }
        }
        assert(0);
    }
};

signed
main()
{
    int n, m, q;
    std::cin >> n >> m >> q;
    tin.resize(n);

    std::vector<Node> all;
    std::vector<std::vector<Node>> g(n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        std::cin >> a >> b;
        a--, b--;
        g[a].push_back(Node(a, b, 0, i));
        g[b].push_back(Node(b, a, 0, i));
    }

    std::vector<std::pair<int, int>> tmp(m);
    for (int i = 0; i < m; i++)
    {
        std::cin >> tmp[i].first >> tmp[i].second;
        tmp[i].first--;
    }
    std::sort(tmp.begin(), tmp.end(), [&](std::pair<int, int> a, std::pair<int, int> b)
              { return a.second < b.second; });
    std::vector<std::vector<int>> need(n - 1);
    for (int i = 0; i < m; i++)
    {
        need[tmp[i].first].push_back(i);
    }
    tin[0] = 0;
    dfs(0, g);
    // for (int i : order)
    // {
    //     std::cout << i << ' ';
    // }
    // std::cout << std::endl;

    std::vector<Query> qu(q);
    for (int i = 0; i < q; i++)
    {
        int start, stop, x, y;
        std::cin >> start >> stop >> x >> y;

        start--, stop--;
        if (tin[start] > tin[stop])
        {
            std::swap(start, stop);
        }
        // std::cout << tin[start] << ' ' << tin[stop] << std::endl;
        qu[i] = Query(tin[start], tin[stop], y, x, i);
    }
    std::sort(qu.begin(), qu.end(), [&](Query a, Query b)
              { 
                if (a.l / LEN != b.l / LEN){
                    return a.l < b.l;
                }
                return a.r < b.r; });
    Corn t(m);
    int l = -1, r = -1;
    std::vector<int> count(n - 1);
    std::vector<int> ans(q);
    for (int i = 0; i < q; i++)
    {
        while (l > qu[i].l)
        {
            l--;
            count[order[l]] += 1;
            count[order[l]] %= 2;
            if (count[order[l]] == 0)
            {
                for (int j : need[order[l]])
                {
                    t.del(j);
                }
            }
            else
            {
                for (int j : need[order[l]])
                {
                    t.add(j, tmp[j].second);
                }
            }
        }

        while (r < qu[i].r)
        {

            r++;
            count[order[r]]++;
            count[order[r]] %= 2;

            if (count[order[r]] == 0)
            {
                for (int j : need[order[r]])
                {
                    t.del(j);
                }
            }
            else
            {
                for (int j : need[order[r]])
                {
                    t.add(j, tmp[j].second);
                }
            }
        }

        while (l < qu[i].l)
        {
            if (l == -1)
            {
                l++;
                continue;
            }
            // std::cout << l << ' ' << order[l] << "djsf; " << ' ' << count[order[l]] << std::endl;
            count[order[l]]--;
            count[order[l]] += 2;
            count[order[l]] %= 2;

            if (count[order[l]] == 0)
            {
                for (int j : need[order[l]])
                {
                    t.del(j);
                }
            }
            else
            {
                for (int j : need[order[l]])
                {
                    t.add(j, tmp[j].second);
                }
            }

            l++;
        }

        while (r > qu[i].r)
        {

            count[order[r]]--;
            count[order[r]] += 2;
            count[order[r]] %= 2;

            if (count[order[r]] == 0)
            {
                for (int j : need[order[r]])
                {
                    t.del(j);
                }
            }
            else
            {
                for (int j : need[order[r]])
                {
                    t.add(j, tmp[j].second);
                }
            }

            r--;
        }

        int need = t.need_gold(qu[i].ser);
        if (need > qu[i].gold)
        {
            ans[qu[i].ind] = -1;
        }
        else
        {
            ans[qu[i].ind] = qu[i].gold - need;
        }
    }
    for (int i = 0; i < q; i++)
    {
        std::cout << ans[i] << std::endl;
    }
}

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