oj.uz

Submission #467888

# Submission time Handle Problem Language Result Execution time Memory
467888 2021-08-25T13:26:20 Z Josia Fountain (eJOI20_fountain) C++14
0 / 100
 135 ms 40840 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};
                
            }
        }
    }
}



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




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});
        

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

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 40840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -