oj.uz

Submission #421657

# Submission time Handle Problem Language Result Execution time Memory
421657 2021-06-09T10:36:26 Z Aldas25 Fountain (eJOI20_fountain) C++14
100 / 100
 1150 ms 35976 KB 
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;

const int MAXN = 500100, MAXK = 20;
const ll INF = 1e16;
const ll MOD = 1e9+7;

int n, q;
ll d[MAXN], c[MAXN];
vii srt;
set<int> cur;

int par[MAXN][MAXK];
ll sum[MAXN][MAXK];

void build () {
    FOR(i, 1, MAXK-1) {
        FOR(v, 1, n) {
            par[v][i] = par[par[v][i-1]][i-1];
            sum[v][i] = sum[v][i-1] + sum[par[v][i-1]][i-1];
        }
    }
}

ll getSum (int v, int i) {
    ll ret = 0ll;
    FOR(j, 0, MAXK-1) {
        if (i & (1<<j)) {
            ret += sum[v][j];
            v = par[v][j];
        }
    }
    return ret;
}

int lift (int v, int i) {
    FOR(j, 0, MAXK-1)
        if (i & (1<<j))
            v = par[v][j];
    return v;
}

int query (int r, ll v) {
    //cout << " query r = " << r << " v = " << v << endl;

    int le = 0, ri = n;
    while (le < ri) {
        int mid = (le+ri)/2;

        //cout << " mid = " << mid << " getSum = " << getSum(r, mid+1) << endl;

        if (getSum(r, mid+1) < v) le = mid+1;
        else ri = mid;
    }
    int ret = lift(r, le);
    if (ret == n+1) return 0;
    else return ret;
}

int main()
{
    FAST_IO;

    cin >> n >> q;
    FOR(i, 1, n) {
        cin >> d[i] >> c[i];
        srt.pb({-d[i], i});
        sum[i][0] = c[i];
    }

    sum[n+1][0] = 1e9+5;

    sort(srt.begin(), srt.end());

    cur.insert(n+1);
    for (auto p : srt) {
        int id = p.s;
        auto it = cur.upper_bound(id);
        par[id][0] = (*it);
        cur.insert(id);
    }

    //FOR(i, 1, n) cout << " i=" << i << " to = " << par[i][0] << endl;

    build ();

    REP(q) {
        int r; ll v;
        cin >> r >> v;
        cout << query(r,v) << "\n";
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 842 ms 33096 KB Output is correct
2 Correct 799 ms 31148 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 4 ms 592 KB Output is correct
6 Correct 3 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 842 ms 33096 KB Output is correct
9 Correct 799 ms 31148 KB Output is correct
10 Correct 3 ms 588 KB Output is correct
11 Correct 320 ms 19568 KB Output is correct
12 Correct 1150 ms 35976 KB Output is correct
13 Correct 910 ms 35692 KB Output is correct
14 Correct 489 ms 34964 KB Output is correct
15 Correct 312 ms 35264 KB Output is correct