Submission #1161661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161661		ace5	Two Currencies (JOI23_currencies)	C++20	100 / 100	3141 ms	62092 KiB

currencies

#include <bits/stdc++.h>

using namespace std;



const int maxn = 300005;
const int sqr = 317;

typedef long long ll;

#define int ll

ll decomp1[maxn];
ll arr1[maxn];
ll decomp2[maxn];
ll arr2[maxn];
int tin[maxn],tout[maxn];
int par[maxn];
int times = 0;
vector<int> eul;
vector<int> edg;
int c[maxn];
vector<vector<pair<int,int>>> g;
int L = 0,R = 0;
int ul = 0,ur = 0;

void modify(int i,int x)
{
    //cout << "mod " << i << ' ' << x << endl;
    arr1[i] += x;
    decomp1[i/sqr] += x;
    arr2[i] += (x > 0 ? 1 : (x < 0 ? -1 : 0));
    decomp2[i/sqr] += (x > 0 ? 1 : (x < 0 ? -1 : 0));
}

void dfs(int v,int p,int pe)
{
    par[v] = p;
    tin[v] = times++;
    eul.push_back(v);
    if(p != -1)
        edg.push_back(pe);
    for(auto [u,i]:g[v])
    {
        if(u != p)
        {
            dfs(u,v,i);
            eul.push_back(v);
            edg.push_back(i);
        }
    }
    tout[v] = times;
}
bool isP(int u,int v)
{
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}
bool ch(int v,bool f)
{
    if(!f)
    {
        swap(ul,ur);
    }
    bool ans = false;
    if(!isP(ul,ur))
    {
        if(v == par[ul])
        {
            ans = false;
        }
        else
        {
            ans = true;
        }
    }
    else
    {
        if(ul == ur)
            ans = true;
        else if(v == par[ul] || !isP(v,ur))
        {
            ans = true;
        }
        else
            ans = false;
    }
    ul = v;
    if(!f)
        swap(ul,ur);
    return ans;
}
void go_ll()
{
    L--;
    if(ch(eul[L],1))
        modify(edg[L],c[edg[L]]);
    else
        modify(edg[L],-c[edg[L]]);
}
void go_lr()
{
    L++;
    if(ch(eul[L],1))
        modify(edg[L-1],c[edg[L-1]]);
    else
        modify(edg[L-1],-c[edg[L-1]]);
}
void go_rl()
{
    R--;
    if(ch(eul[R],0))
        modify(edg[R],c[edg[R]]);
    else
        modify(edg[R],-c[edg[R]]);
}
void go_rr()
{
    R++;
    if(ch(eul[R],0))
        modify(edg[R-1],c[edg[R-1]]);
    else
        modify(edg[R-1],-c[edg[R-1]]);
}
struct que
{
    que(ll _s,ll _t,ll _x,ll _y,ll _i){s = _s;t = _t;x = _x;y = _y;i = _i;};
    ll s,t,x,y,i;
    bool operator < (const que & oth){return (s/sqr != oth.s/sqr ? s < oth.s : t < oth.t);};
};

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    vector<pair<int,int>> e;
    vector<vector<int>> ch(n-1);
    for(int j = 0;j < n-1;++j)
    {
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        e.push_back({a,b});
    }
    vector<pair<int,int>> ed;
    for(int j = 0;j < m;++j)
    {
        int p,c;
        cin >> p >> c;
        p--;
        ed.push_back({c,p});
    }
    sort(ed.begin(),ed.end());
    for(int j = 0;j < ed.size();++j)
    {
        c[j+1] = ed[j].first;
        ch[ed[j].second].push_back(j+1);
    }
    int yk = n;
    vector<pair<pair<int,int>,int>> ee;
    for(int j = 0;j < n-1;++j)
    {
        if(ch[j].size() == 0)
        {
            ee.push_back({{e[j].first,e[j].second},0});
        }
        else
        {
            int st = e[j].first,en = e[j].second;
            for(int y = 0;y < ch[j].size();++y)
            {
                int fv = (y == 0 ? st : yk++);
                int sv = (y+1 == ch[j].size() ? en : yk);
                ee.push_back({{fv,sv},ch[j][y]});
            }
        }
    }
    g.resize(yk);
    for(int u=  0;u < ee.size();++u)
    {
        int v1 = ee[u].first.first,v2 = ee[u].first.second,i = ee[u].second;
        //cout << v1 << ' ' << v2 << ' ' << i << ' ' << c[i] << "\n";
        g[v1].push_back({v2,i});
        g[v2].push_back({v1,i});
    }
    dfs(0,-1,-1);
    vector<int> pos(yk);
    for(int y = 0;y < eul.size();++y)
    {
        pos[eul[y]] = y;
    }
    vector<que> queries;
    for(int i =0;i < q;++i)
    {
        ll s,t,x,y;
        cin >> s >> t >> x >> y;
        s--;
        t--;
        s = pos[s];
        t = pos[t];
        if(s > t)
            swap(s,t);
        //cout << s << ' ' << t << endl;
        queries.push_back(que(s,t,x,y,i));
    }
    sort(queries.begin(),queries.end());
    int res[q];
    for(int j = 0;j < queries.size();++j)
    {
        int s = queries[j].s,t = queries[j].t,x = queries[j].x,y = queries[j].y,ii = queries[j].i;
        while(L > s)
            go_ll();
        while(R < t)
            go_rr();
        while(L < s)
            go_lr();
        while(R > t)
            go_rl();
       // cout << "! " << s << ' ' << t << ' ' << x << ' ' << y << ' ' << decomp1[0] << ' ' << arr2[1] << endl;
        ll sum = 0;
        ll ans = 0;
        int pos = m+1;
        for(int i = 0;i < sqr;++i)
        {
            if(sum+decomp1[i] <= y)
            {
                sum += decomp1[i];
            }
            else
            {
                for(int l = i*sqr;l < (i+1)*sqr;++l)
                {
                    //cout << arr1[l] << endl;
                    if(sum + arr1[l] <= y)
                    {
                        sum += arr1[l];
                    }
                    else
                    {
                        pos = l;
                        break;
                    }
                }
                break;
            }
        }
        //cout << pos << endl;
        while(pos < m+1 && pos%sqr)
        {
            ans += arr2[pos++];
        }
        //cout << ans << endl;
        while(pos < m+1)
        {
            ans += decomp2[pos/sqr];
            pos += sqr;
        }
        res[ii] = (x >= ans ? x-ans : -1);
    }
    for(int i = 0;i < q;++i)
        cout << res[i] << "\n";
}

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