Submission #915217

#	Time	Username	Problem	Language	Result	Execution time	Memory
915217		berr	Two Currencies (JOI23_currencies)	C++17	100 / 100	1868 ms	149724 KiB

currencies

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

#define int long long
const int mod = 1e9+7;

struct segtree{
    using T = array<int, 2>;
    vector<T> st;
    vector<int> ar;
    int n, tl, tr;

    T base = {0, 0};

    segtree(){
        st.resize(1);
    };

    T merge(T x, T y){
        x[0] += y[0]; x[1] += y[1];
        return x;
    }

    segtree(vector<int> a){
        ar = a;
        n = a.size();

        st.resize(n*4, base);

        build(1, 0, n-1);
    }

    void build(int v, int l, int r){
        if(l==r){
            st[v] = {0, ar[l]};
        }
        else if(l < r){
            int mid = (l + r) / 2;

            build(v*2, l, mid);
            build(v*2+1, mid+1, r);

            st[v] = merge(st[v*2], st[v*2+1]);  
        }
    }

    void upd(int v, int l, int r, int pos, T x){
        if(l==r){
            st[v] = merge(st[v], x);
        }
        else if(l<r){
            int mid = (l+r) / 2;

            if (pos <= mid)upd(v*2, l, mid, pos, x);
            else upd(v*2+1, mid+1, r, pos, x);

            st[v] = merge(st[v*2], st[v*2+1]);
        }

    }
    void upd(int v, T gh){
        upd(1, 0, n-1, v, gh);
    }

    T get(int v, int l, int r){
        if(r<tl || l > tr) return base;
        else if(l>=tl && r<= tr){
            return st[v];
        } 
        else{
            int mid = (l+r) / 2;

            return merge(get(v*2, l, mid), get(v*2+1, mid+1, r));
        }
    }

    T operator()(int l, int r){
        tl = l; tr = r;
        if(l>r) return {0, 0};

        return get(1, 0, n-1);
    }

};
vector<segtree> st;

struct hld{

    vector<vector<array<int, 2>>> g;
    vector<vector<int>> chain;
    vector<int> s, c, d, p_node, p_edge, val;
    vector<int> pos_edge, ind_edge;
    vector<int> pos_node, ind_node;
    int n;
    
    hld(){};

    hld(int _n, vector<vector<array<int, 2>>>a, vector<int> v){
        n = _n; g = a;
        s.resize(n, 1); d.resize(n);
        pos_edge.resize(n); ind_edge.resize(n);
        pos_node.resize(n); ind_node.resize(n);

        p_edge.resize(n);  
        p_node.resize(n);

        val = v;
        d[0] = -1;
        dfs(0, 0); dfs2(0, 0);
        p_edge[0] = n-1;
        for(int i=0; i<chain.size(); i++){
            reverse(chain[i].begin(), chain[i].end());

            vector<int> x;
            for(int l=0; l<chain[i].size(); l++){
                int node = chain[i][l];
                int edge  = p_edge[node];

                ind_edge[edge] = ind_node[node] = l;
                pos_edge[edge] = pos_node[node] = i;


                x.push_back(val[edge]);
            }

            st.push_back(segtree(x));
        }
    };

    void dfs(int v, int par){
        p_node[v] = par;

        for(int i = 0; i <g[v].size(); i++){
            auto [x, y] = g[v][i];
            
            if(x!=par){
                dfs(x, v);
                p_edge[x] = y;
                s[v] += s[x];
                if(s[x] > s[g[v][0][0]]||g[v][0][0]==par){
                    swap(g[v][0], g[v][i]);
                }
            }
        }

    }

    void dfs2(int v, int p){
        c.push_back(v);

        d[v] = d[p]+1;
        for(auto &[x, y]: g[v]){
            if(x==p) continue;
            dfs2(x, v);
        }

        if(g[v].size()==1 && v!=p && c.size()){
            chain.push_back(c);
            c.clear();
        }
    }


    array<int, 2> merge(array<int, 2> x, array<int, 2> y){
        x[0] += y[0]; x[1] += y[1];
        return x;
    }
    array<int, 2> get(int v, int u){

        int pv = pos_node[v], pu = pos_node[u];
        array<int, 2> gh ={0, 0};

        while(pv != pu){

            if(d[chain[pu].back()] > d[chain[pv].back()]){
                swap(pv, pu);
                swap(u, v);
            }

            gh=merge(gh, st[pv](ind_node[v], ind_node[chain[pv].back()]));
            v = p_node[chain[pv].back()];
            pv = pos_node[v];
        }

        if(d[v] <d[u]) swap(u, v);

        gh = merge(gh, st[pv](ind_node[v], ind_node[u]-1));

        return gh;
    }

};


hld h;

struct comparer{
    int k = 0;
    int n;
    vector<array<int, 2>> val;
    vector<int> ind;
  
    comparer(vector<array<int, 2>> v){
        n = v.size();
        val = v;
        k = 0;

        ind.resize(n);

        iota(ind.begin(), ind.end(), 0);
        sort(ind.begin(), ind.end(), [&](int x, int y){
            return val[x][1] > val[y][1];
        });


    };

    void operator++(){
        int pf = val[ind[k]][0];
        int pos= h.pos_edge[pf];
        int id = h.ind_edge[pf];
        auto x = st[pos](id, id);

        st[pos].upd(id, {1, -val[ind[k]][1]});
         x = st[pos](id, id);

        k++;
    }
    void operator--(){
        k--;

        int pf = val[ind[k]][0];
        int pos= h.pos_edge[pf];
        int id = h.ind_edge[pf];

        st[pos].upd(id, {-1, val[ind[k]][1]});
    }

};

struct query{
    int u=0, v=0;
    int x=0, y=0; 
    int ind=0;

    query(){};

    query(array<int, 5> s){
        u=s[0]; v = s[1]; x=s[2]; y=s[3];
        ind = s[4];
    }
    bool check(){

        auto a = h.get(u, v);
        return (a[0]<x && a[1]>y); 
    }

    int check2(){
        auto a = h.get(u, v);

        if(a[0]<=x && a[1]<=y){
            return x-a[0];
        }
        return -1;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, q; cin >> n >> m >> q;
    n++;
    vector<int> val(n);
    vector<array<int, 2>> val2(m);
    vector<vector<array<int, 2>>> g(n);
    vector<array<int, 2>> e(n-2);
    
    for (auto &[x, y]: e){
        cin >> x >> y;
        x--; y--;
    }


    e.push_back({0, n-1});

    for(int i=0; i<m; i++){
        int z, c; cin >> z >> c;
        val[z-1] += c;    
        val2[i]={z-1, c};     
    }   

    for(int i=0; i<n; i++){
        if(val[i]==0) val2.push_back({i, 0});
    }

    for(int i=0; i<n-1; i++){
        auto [x, y]=e[i];
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }

    h = hld(n, g, val);
    comparer cmp(val2);

    vector<query> qu(q);

    for(int i=0; i<q; i++){
        array<int, 5> f;
        for(int l=0; l<4; l++) cin >> f[l];

        f[0]--; f[1]--;
        f[4] = i;
        qu[i] = query(f);


    }   

    vector<int> ans(q);

    auto rec = [&](vector<query> x, int l, int r,auto &&rec)->void{
      //  cout<<l<<" "<<r<<"\n";
        if(l==r){

            while(cmp.k<l){
                ++cmp;
            }

            while(cmp.k>l){
                --cmp;
            }

            for(auto i: x){
           //     cout<<i.ind<<" "<<cmp.k<<"a\n";
                ans[i.ind] = i.check2();
            }
        }
        else if(l<r){
            vector<query> a, b;
            int mid = (l+r)/2;
           while(cmp.k < mid){
                ++cmp;
            }

            while(cmp.k > mid){
                --cmp;
            }
            //cout<<l<<" "<<r<<"\n";
            for(auto i: x){
                if(i.check()) a.push_back(i);
                else b.push_back(i);
            }

            if(a.size())
                rec(a, mid+1, r, rec);
            if(b.size())
                rec(b, l, mid, rec);

        }

    };

    rec(qu, 0, val2.size()-1, rec);
    for(auto i: ans) cout<<i<<"\n";
}

Compilation message (stderr)

currencies.cpp: In constructor 'hld::hld(long long int, std::vector<std::vector<std::array<long long int, 2> > >, std::vector<long long int>)':
currencies.cpp:111:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int i=0; i<chain.size(); i++){
      |                      ~^~~~~~~~~~~~~
currencies.cpp:115:27: 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]
  115 |             for(int l=0; l<chain[i].size(); l++){
      |                          ~^~~~~~~~~~~~~~~~
currencies.cpp: In member function 'void hld::dfs(long long int, long long int)':
currencies.cpp:133:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         for(int i = 0; i <g[v].size(); i++){
      |                        ~~^~~~~~~~~~~~

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