oj.uz

Submission #562582

# Submission time Handle Problem Language Result Execution time Memory
562582 2022-05-14T17:05:58 Z illyakr Fountain (eJOI20_fountain) C++14
100 / 100
 454 ms 64204 KB 
//#pragma GCC optimize("inline,Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,avx,abm")
#include <bits/stdc++.h>
#define ll long long
#define int ll
typedef long double ld;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define y0 dfgoert
#define y1 kjsjofd
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1000000007;
const int INF1e9 = 1010101010;
const int INF1e18 = 1010101010101010101;
const ld PI =  3.14159265358979323846264338327950288419716939937510;

int n, q;
int d[101010], c[101010];
int t[401010];
void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = vl;
        return;
    }
    int vm = (vl + vr) / 2;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
    if (d[t[2 * v]] > d[t[2 * v + 1]])
        t[v] = t[2 * v];
    else
        t[v] = t[2 * v + 1];
}

int gt(int v, int vl, int vr, int l, int r, int cur) {
    if (d[t[v]] <= cur)return INF1e9;
    if (vl == vr)return t[v];

    int vm = (vl + vr) / 2;
    if (l <= vl && vr <= r) {
        if (cur < d[t[2 * v]])return gt(2 * v, vl, vm, l, r, cur);
        return gt(2 * v + 1, vm + 1, vr, l, r, cur);
    }
    if (r < vl || vr < l)return INF1e9;
    return min(gt(2 * v, vl, vm, l, r, cur), gt(2 * v + 1, vm + 1, vr, l, r, cur));
}
vector<pair<int, int> > g[101010];
int rmq[30][101010];
int can[30][101010];
int to[101010];

int tin[101010];
int tout[101010];
int T = 1;
void dfs(int v) {
    if (tin[v] != 0)return;
    tin[v] = T++;
//    cout << v << " --> " << to[v] << endl;
    if (to[v] == 0) {
        for (int i = 0; i < 30; i++) {
            rmq[i][v] = v;
            can[i][v] = INF1e9;
        }
        return;
    }
    dfs(to[v]);
    tout[v] = T++;

    rmq[0][v] = to[v];
    can[0][v] = c[v];

    for (int i = 1; i < 30; i++) {
        rmq[i][v] = rmq[i - 1][rmq[i - 1][v]];
        can[i][v] = can[i - 1][v] + can[i - 1][rmq[i - 1][v]];
    }
}

int uplf(int v, int li) {
//    cout << v << " " << li << " !!" << endl;
    for (int i = 29; i >= 0; i--) {
//        cout << i << ": " << can[i][v] << "   " << rmq[i][v] << "      ??? " << li << endl;
        if (li > can[i][v]) {
            li -= can[i][v];
            v = rmq[i][v];
            continue;
        }
    }
    return v;
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> d[i] >> c[i];
    d[n + 1] = INF1e18;c[n + 1] = INF1e18;
    n++;

    build(1, 1, n);
    for (int i = n - 1; i >= 1; i--) {
        to[i] = gt(1, 1, n, i + 1, n, d[i]);
    }
    dfs(1);
    for (int i = 1; i <= n; i++) {
        if (tin[i] == 0)
            dfs(i);
    }
    while (q--) {
        int R, V;
        cin >> R >> V;
        int ans = uplf(R, V);
        if (ans == n)cout << 0 << '\n';
        else cout << ans << '\n';
    }
//    for (int i = 1; i <= n; i++) {
//        for (int j = 0; j < 5; j++) {
//            cout << setw(2) << rmq[j][i];
//            cout << setw(5) << can[j][i];
//            cout << "        ";
//        }
//        cout << endl;
//    }
}

int32_t main() {
    fast
    int t = 1;
//    cin >> t;
    for (int id = 1; id <= t; id++) {
//        cout << "Case " << id << ": ";
        solve();
    }
}
/**
10 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10


6 5
4 10
6 8
3 5
4 14
10 9
4 20
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 3 ms 3668 KB Output is correct
6 Correct 3 ms 3620 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 60008 KB Output is correct
2 Correct 321 ms 56216 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3284 KB Output is correct
3 Correct 3 ms 3404 KB Output is correct
4 Correct 3 ms 3540 KB Output is correct
5 Correct 3 ms 3668 KB Output is correct
6 Correct 3 ms 3620 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 311 ms 60008 KB Output is correct
9 Correct 321 ms 56216 KB Output is correct
10 Correct 3 ms 3536 KB Output is correct
11 Correct 127 ms 34380 KB Output is correct
12 Correct 454 ms 64204 KB Output is correct
13 Correct 325 ms 60760 KB Output is correct
14 Correct 271 ms 59888 KB Output is correct
15 Correct 196 ms 60288 KB Output is correct