Submission #1181727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181727		zadniprovska	Fountain (eJOI20_fountain)	C++20	30 / 100	77 ms	14920 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

#define el '\n'
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<long long, long long>
#define ppll pair< long long, pair<long long, long long> >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()

const ll DIM = 2e5+7;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxlog = 20;

struct Node {
    ll d, cap, id;
};

Node a[DIM];
vector<pll> q[DIM];
ll answer[DIM], T[4*DIM];

bool cmp (Node t1, Node t2) {
    if (t1.d == t2.d) return t1.id < t2.id;
    return t1.d > t2.d;
}

void update(ll v, ll tl, ll tr, ll pos, ll val) {

    if (pos < tl || tr < pos) return;

    if (tl == tr) {
        T[v] = val;
        return;
    }

    ll tm = (tl + tr) >> 1;
    update(2*v+1, tl, tm, pos, val);
    update(2*v+2, tm+1, tr, pos, val);
    T[v] = T[2*v+1] + T[2*v+2];

}

ll query1 (ll v, ll tl, ll tr, ll R) {

    if (R < tl) return 0;

    if (tr <= R) return T[v];

    ll tm = (tl + tr) >> 1;
    return query1(2*v+1, tl, tm, R) + query1(2*v+2, tm+1, tr, R);

}

ll query2 (ll v, ll tl, ll tr, ll val) {

    if (tl == tr) return tl;

    ll tm = (tl + tr) >> 1;
    if (T[2*v+1] >= val) return query2(2*v+1, tl, tm, val);
    return query2(2*v+2, tm+1, tr, val - T[2*v+1]);

}

void solve() {

    ll n, nq;
    cin >> n >> nq;

    for (int i=1; i<=n; i++) {
        cin >> a[i].d >> a[i].cap;
        a[i].id = i;
    }
    sort(a+1, a+1+n, cmp);

    for (int i=1; i<=nq; i++) {
        ll pos, val;
        cin >> pos >> val;

        q[pos].pb({val, i});
    }


    update(0, 1, n+1, n+1, INF);
    for (int i=1; i<=n; i++) {
        //cout << "/" << a[i].id << " " << a[i].d << " " << a[i].cap  << el;

        update(0, 1, n+1, a[i].id, a[i].cap);


        for (auto [val, num] : q[a[i].id]) {

            ll bef;
            if (a[i].id != 1) bef = query1(0, 1, n+1, a[i].id-1);
            else bef = 0;

            ll res = query2(0, 1, n+1, bef+val);

            if (res == n+1) res = 0;
            answer[num] = res;

        }

    }

    for (int i=1; i<=nq; i++) {
        cout << answer[i] << el;
    }


}



signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    //freopen("nocross.in", "r", stdin);
    //freopen("nocross.out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--){
        solve();
    }
    return 0;

}
;

• Subtask 1: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40