제출 #467952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467952		Josia	Fountain (eJOI20_fountain)	C++17	100 / 100	541 ms	45456 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40