Submission #856750

#	Time	Username	Problem	Language	Result	Execution time	Memory
856750		bkhanh	Two Currencies (JOI23_currencies)	C++14	100 / 100	3716 ms	51368 KiB

currencies

#include<bits/stdc++.h>
using namespace std;    

namespace Solve
{
    #define int long long
    const int M = 1e5 + 1;
    const int Srt = 350;

    typedef tuple<long long, long long, long long> ox;
    vector<ox> idVal;

    long long ans[M];
    
    struct Node
    {
        int nxt, id;
    };

    struct Query
    {
        long long Comp, id, x, y, z, w;

        bool operator < (const Query that)
        {
            if(Comp != that.Comp) return Comp < that.Comp;
            if(y != that.y) return y < that.y;
            return x < that.x;
        }
    };

    vector<Query> List;
    int vis[2000001];
    vector<int> list[M];
    int h[M], par[M][21];
    int timeIn[M], timeOut[M];
    vector<long long> valRag;
    int timeDFS;

    long long Sum[2000001];
    long long node[2000001];
    int pos[M];

    vector<Node> adj[M];

    void DFS(int u, int par)
    {
        h[u] = h[par] + 1;
        timeIn[u] = timeDFS++;
        pos[u] = valRag.size();

        for(auto info: adj[u])
        {
            if(info.nxt != par)
            {
                for(auto c: list[info.id]) valRag.push_back(c);
                DFS(info.nxt, u);
                for(auto c: list[info.id]) valRag.push_back(c);
            }
        }

        timeOut[u] = timeDFS;
    }

    void Update(int pos, long long val)
    {
        pos += (1 << 18);

        while(pos)
        {
            Sum[pos] += val;
            node[pos] += val > 0 ? 1 : -1;
            pos /= 2;
        }
    }

    void Up(int id)
    {
        if(!vis[id])
        {
            Update(id, get<0>(idVal[id]));
        }
        else
        {
            Update(id, (-1LL) * get<0>(idVal[id]));
        }

        vis[id] ^= 1;
    }

    long long cal(int id, long long val)
    {
        if(id >= (1 << 18))
        {
            return 0;
        }

        if(Sum[id * 2] <= val) return cal(id * 2 + 1, val - Sum[2 * id]) + node[2 * id];
        else return cal(id * 2, val);
    }

    void solve()
    {
        int n, m, q;
        cin >> n >> m >> q;

        for(int i = 1; i < n; i++)
        {
            int u, v;
            cin >> u >> v;
            adj[u].push_back({v, i});
            adj[v].push_back({u, i});
        }

        for(int i = 1; i <= m; i++)
        {
            long long id, c;
            cin >> id >> c;

            idVal.push_back({c, id, list[id].size()});
            list[id].push_back(c);
        }

        idVal.push_back({0, -1, -1});
        sort(idVal.begin(), idVal.end());

        for(int i = 1; i < idVal.size(); i++)
        {
            auto t = idVal[i];
            list[get<1>(t)][get<2>(t)] = i;
        }

        DFS(1, 1);

        for(int i = 1; i <= q; i++)
        {
            int x, y, z, w;
            cin >> x >> y >> z >> w;

            x = pos[x];
            y = pos[y];

            if(x > y) swap(x, y);

            List.push_back({x / Srt, i, x, y, z, w});
        }

        memset(ans, -1, sizeof ans);
        sort(List.begin(), List.end());

        int l = 0, r = 0;

        for(auto info: List)
        {
            while(l < info.x)
            {
                Up(valRag[l]);
                l++;
            }

            while(info.x < l)
            {
                l--;
                Up(valRag[l]);
            }

            while(r < info.y)
            {
                Up(valRag[r]);
                r++;
            }

            while(info.y < r)
            {
                r--;
                Up(valRag[r]);
            }

            long long Val = cal(1, info.w);

            if(node[1] > info.z + Val)
            {
                ans[info.id] = -1;
            }
            else
            {
                ans[info.id] = info.z + Val - node[1];
            }
        }

        
        for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
    }
}

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

    Solve::solve();
}

Compilation message (stderr)

currencies.cpp: In function 'void Solve::solve()':
currencies.cpp:127:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         for(int i = 1; i < idVal.size(); i++)
      |                        ~~^~~~~~~~~~~~~~
currencies.cpp: At global scope:
currencies.cpp:196:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  196 | main()
      | ^~~~

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