oj.uz

Submission #467503

# Submission time Handle Problem Language Result Execution time Memory
467503 2021-08-23T10:38:21 Z shmad Fountain (eJOI20_fountain) C++17
100 / 100
 392 ms 39940 KB 

#include <bits/stdc++.h>
 
#define nl '\n'
#define pb push_back
#define E exit(0)
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define sz(s) (int)(s).size()
#define ll long long
#define int ll
#define oioi ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define vt vector
#define dbg(x) cerr << #x << " = " << x << nl

using namespace std;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;
 
const int N = 1e6 + 5;
const int INF = 1e18 + 7;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const int B = 800;

int n, q, up[N][21], wtr[N][21], diam[N];

int get (int a, int b) {
    for (int i = 20; i >= 0; i--) {
        if (wtr[a][i] < b && wtr[a][i]) b -= wtr[a][i], a = up[a][i];
    }
    return a;
}

void solve () {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> diam[i] >> wtr[i][0];
    stack<int> s;
    s.push(0);
    diam[0] = INF;
    for (int i = n; i >= 1; i--) {
        while (diam[s.top()] <= diam[i]) s.pop();
        up[i][0] = s.top();
        s.push(i);
    }
    up[0][0] = wtr[0][0] = 0;
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= n; i++) {
            int jump = up[i][j - 1];
            up[i][j] = up[jump][j - 1];
            wtr[i][j] = wtr[i][j - 1] + wtr[jump][j - 1];
        }
    }
    while (q--) {
        int r, v;
        cin >> r >> v;
        cout << get(r, v) << nl;
    }
    cout << nl;
}

int test = 1;
 
signed main () {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    oioi
//  cin >> test; 
    while (test--) solve();
    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 4 ms 588 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 716 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 272 ms 34700 KB Output is correct
2 Correct 337 ms 32220 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 4 ms 588 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 272 ms 34700 KB Output is correct
9 Correct 337 ms 32220 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 134 ms 21464 KB Output is correct
12 Correct 392 ms 39940 KB Output is correct
13 Correct 305 ms 38852 KB Output is correct
14 Correct 224 ms 38092 KB Output is correct
15 Correct 179 ms 38340 KB Output is correct