oj.uz

Submission #444647

# Submission time Handle Problem Language Result Execution time Memory
444647 2021-07-14T13:55:48 Z shrimb Fountain (eJOI20_fountain) C++17
100 / 100
 410 ms 40760 KB 
#include"bits/stdc++.h"
#define int long long
#define endl '\n'
using namespace std;
pair<int,int> sparse[100001][20]; // {node, capacity}
 
signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1 ; i <= n ; i++) {
        for (int j = 0 ; j < 20 ; j++) sparse[i][j] = {-1, INT_MAX};
    }
    pair<int,int> arr[n + 1];
    vector<pair<int,int>> v; // {radius, index}
    vector<int> E;
    set<int> s;
    for (int i = 1 ; i <= n ; i++) {
        cin >> arr[i].first >> arr[i].second;
        v.push_back({arr[i].first, i});
    }
    sort(v.begin(), v.end());
 
    for (int i = n - 1 ; i >= 0 ; i--) {
        auto it = s.lower_bound(v[i].second);
        sparse[v[i].second][0] = {(it == s.end() ? -1 : *it), arr[v[i].second].second};
        E.push_back(v[i].second);
        // s.insert(v[i].second);
        if (i == 0 || v[i].first != v[i-1].first) {
            for (int j : E) s.insert(j);
            E.clear();
        }
    }
 
    for (int i = n ; i >= 1 ; i--) {
        for (int j = 1 ; sparse[i][j-1].first != -1 ; j++) {
            sparse[i][j] = {sparse[sparse[i][j-1].first][j-1].first, sparse[i][j-1].second + sparse[sparse[i][j-1].first][j-1].second};
        }
    }
 
    while (q--) {
        int s, x;
        cin >> s >> x;
        for (int i = 19 ; i >= 0 ; i--) {
            if (sparse[s][i].second < x) {
              x -= sparse[s][i].second;
                s = sparse[s][i].first;
                
            }
        }
        cout << (s == -1 ? 0 : s) << endl;
    }
}
//    5   4
// 1 -> 2 -> 3

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 38312 KB Output is correct
2 Correct 287 ms 35384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 264 ms 38312 KB Output is correct
9 Correct 287 ms 35384 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 122 ms 22532 KB Output is correct
12 Correct 410 ms 40720 KB Output is correct
13 Correct 279 ms 40760 KB Output is correct
14 Correct 214 ms 40568 KB Output is correct
15 Correct 163 ms 40632 KB Output is correct