Submission #1247630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247630		nerrrmin	Two Currencies (JOI23_currencies)	C++20	30 / 100	994 ms	142896 KiB

currencies

#include<bits/stdc++.h>
#define pb push_back
#define endl '\n'
using namespace std;
const long long maxn = 3e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m, q;
vector < pair < long long , long long > > g[maxn];
vector < pair < long long , long long > > u;
long long a[maxn], b[maxn];
struct persistent_sgt
{
    struct node
    {
        long long val, cnt, l, r;
        node()
        {
            val = 0;
            cnt = 0;
            l = 0;
            r = 0;
        };
        node(long long _val, long long _cnt, long long _l, long long _r)
        {
            val = _val;
            cnt = _cnt;
            l = _l;
            r = _r;
        }
    };
    long long n;
    vector < node > t;
    long long tmr = 1;

    node join (long long l, long long r)
    {
        return node(t[l].val + t[r].val, t[l].cnt + t[r].cnt, l, r);
    }
    long long build(long long i, long long l, long long r)
    {
        if(l == r)
        {
            t[tmr] = node(0, 0, 0, 0);
            tmr ++;
            return tmr - 1;
        }
        long long mid = (l + r)/2;
        t[tmr] = join(build(2*i, l, mid), build(2*i+1, mid+1, r));
        tmr ++;
        return tmr - 1;
    }
    long long upd(long long i, long long l, long long r, long long upos, long long uval)
    {
        if(l == r)
        {
            t[tmr] = node(t[i].val + uval, t[i].cnt + 1, 0, 0);
            tmr ++;
            return tmr - 1;
        }
        long long mid = (l + r)/2;
        if(upos <= mid)t[tmr] = join(upd(t[i].l, l, mid, upos, uval), t[i].r);
        else t[tmr] = join(t[i].l, upd(t[i].r, mid+1, r, upos, uval));
        tmr ++;
        return tmr - 1;
    }
    long long query(long long i, long long l, long long r, long long ql, long long qr)
    {
        if(qr < l || ql > r)return 0;
        if(ql <= l && r <= qr)return t[i].val;
        long long mid = (l + r)/2;
        return query(t[i].l, l, mid, ql, qr) + query(t[i].r, mid+1, r, ql, qr);
    }
    long long query_cnt(long long i, long long l, long long r, long long ql, long long qr)
    {
        if(qr < l || ql > r)return 0;
        if(ql <= l && r <= qr)return t[i].cnt;
        long long mid = (l + r)/2;
        return query_cnt(t[i].l, l, mid, ql, qr) + query_cnt(t[i].r, mid+1, r, ql, qr);
    }
    void prep(long long sz, long long maxt)
    {
        n = sz;
        t.resize(maxt);
    }
    long long run_build()
    {
        return build(1, 1, n);
    }
    long long run_upd(long long root, long long upos, long long uval)
    {
        return upd(root, 1, n, upos, uval);
    }
    long long run_query(long long root, long long ql, long long qr)
    {
        return query(root, 1, n, ql, qr);
    }
    long long run_query_cnt(long long root, long long ql, long long qr)
    {
        return query_cnt(root, 1, n, ql, qr);
    }
};
persistent_sgt p;
vector < long long > roots;
int main()
{
    speed();

    cin >> n >> m >> q;
    for (long long i = 1; i < n; ++ i)
    {
        long long from, to;
        cin >> from >> to;
        a[i] = from;
        b[i] = to;
        g[from].pb({to, i}); /// ?
        g[to].pb({from, i});
    }

    for (long long i = 1; i <= m; ++ i)
    {
        long long road, silver;
        cin >> road >> silver;

        u.pb(make_pair(silver, road));
    }
    p.prep(n, 40*n);

    roots.pb(p.run_build());
    long long last = roots.back();
    sort(u.begin(), u.end());
    for (auto &[silver, road]: u)
    {
        long long setpos = max(a[road], b[road]);
        long long nr = p.run_upd(last, setpos, silver);
        roots.pb(nr);
        last = nr;
    }


    assert(roots.size() == m + 1);
    //cout << "last is " << last << endl;
    while(q --)
    {
        long long si, ti, xi, yi;
        cin >> si >> ti >> xi >> yi;

        if(si > ti)swap(si, ti);

        long long tot = p.run_query_cnt(last, si+1, ti);
        long long l = 0, r = roots.size()-1, mid, ans = 0; /// tyrsq nai posledniq moment v koito sumata v range-a mi e <= yi
        while(l <= r)
        {
            mid = (l + r)/2;
            long long sum = p.run_query(roots[mid], si+1, ti);
            if(sum <= yi)
            {
                l = mid + 1;
                ans = p.run_query_cnt(roots[mid], si+1, ti);
            }
            else r = mid - 1;
        }

       // cout << tot << " " << ans << endl;
        if(xi < (tot-ans))cout << -1 << endl;
        else cout << xi - (tot - ans) << endl;
    }
    return 0;
}

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