oj.uz

Submission #467952

# Submission time Handle Problem Language Result Execution time Memory
467952 2021-08-25T17:41:55 Z Josia Fountain (eJOI20_fountain) C++17
100 / 100
 541 ms 45456 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;

#define int int64_t


vector<vector<pair<int, int>>> up;    // vertex, capacity


void init(vector<int>& graph, vector<int>& capacities) {
    int n = graph.size();
    up.assign(n+1, vector<pair<int, int>>((int)(log2(n+1))+2, {-1, -1}));
    
    
    for (int j = 0; j<log2(n+1)+1; j++) {
        for (int i = 0; i<n+1; i++) {
            int c = capacities[i];
            if (j == 0) {
                if (i<n) up[i][j] = {graph[i], c+capacities[graph[i]]};
                else up[i][j] = {i, INT32_MAX};
            }
            
            else {
                up[i][j] = {up[up[i][j-1].first][j-1].first, up[up[i][j-1].first][j-1].second+up[i][j-1].second-capacities[up[i][j-1].first]};
                
            }
        }
    }
}



int querry(vector<int>& graph, vector<int>& capacities, int pos, int amount) {
    int e = -1;
    while (up[pos][e+1].second <= amount) {
        e++;
    }
    if (amount <= capacities[pos]) return pos;
    
    if (e==-1) return querry(graph, capacities, graph[pos], amount-capacities[pos]);
    
    else return querry(graph, capacities, up[pos][e].first, amount-up[pos][e].second+capacities[up[pos][e].first]);
}




signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q; cin >> n >> q;
    
    vector<pair<int, int>> fountain;
    vector<int> capacities;
    vector<pair<int, int>> querries;

    for (int i = 0; i<n; i++) {
        int d, c; cin >> d >> c;
        fountain.push_back({d, c});
        capacities.push_back(c);
    }
    
    for (int i = 0; i<q; i++) {
        int r, v; cin >> r >> v;
        querries.push_back({r, v});
    }
    
    
    vector<int> graph(n);

    vector<pair<int, int>> stck = {{n, INT32_MAX}};
    
    for (int i = n-1; i>=0; i--) {
        while (fountain[i].first >= stck.back().second) stck.pop_back();
        
        graph[i] = stck.back().first;
        stck.push_back({i, fountain[i].first});
        

    }
    
//    for (int i: graph) {
//        cout << i << " ";
//    }
//    cout << "\n";
    
    
    capacities.push_back(INT32_MAX);
 
    init(graph, capacities);
    
    for (auto i: querries) {
        int res = querry(graph, capacities, i.first-1, i.second);
        int output = (res==n) ? (0) : (res+1);
        cout << output << "\n";
    }
    
    
    

    return 0;
}

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 2 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 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 345 ms 38440 KB Output is correct
2 Correct 393 ms 36092 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 2 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 345 ms 38440 KB Output is correct
9 Correct 393 ms 36092 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 137 ms 22940 KB Output is correct
12 Correct 541 ms 45456 KB Output is correct
13 Correct 353 ms 43916 KB Output is correct
14 Correct 242 ms 42788 KB Output is correct
15 Correct 171 ms 43184 KB Output is correct