Submission #536063

#	Time	Username	Problem	Language	Result	Execution time	Memory
536063		Itamar	Fountain (eJOI20_fountain)	C++14	100 / 100	303 ms	19288 KiB

fountain

#include <map>
#include <iostream>
using namespace std;
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#define ll long long
#define vi vector<int> 
#define vll vector<ll>
#define pi pair<int,int> 
#define pll pair<ll,ll>

pi padre[200000][17];
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, qu;
    cin >> n >> qu;

    priority_queue<pi,vector<pi>,greater<pi>> q;
    vi cost(n);
    for (int i = 0; i < n; i++) {
        int d, c;
        cin >> d >> c;
        cost[i] = c;
        q.push({ d,i });
        pi p = q.top();
        while (p.first < d) {
            padre[p.second][0]={i,cost[p.second]};
            q.pop();
            p = q.top();
        }
    }
    while (!q.empty()) {
        padre[q.top().second][0] = { -1,cost[q.top().second]};
        q.pop();
    }
    for (int i = 1; i < 17; i++) {
        for (int j = 0; j < n; j++) {
            pi prev = padre[j][i - 1];
            if (prev.first == -1)
                padre[j][i] = prev;
            else
                padre[j][i] = { padre[prev.first][i - 1].first,padre[prev.first][i-1].second + prev.second};
        }
    }
    for (int i = 0; i < qu; i++) {
        int r, v;
        cin >> r >> v;
        r--;
        for (int it = 16; it >= 0; it--) {
            if (padre[r][it].second < v) {
                v -= padre[r][it].second;
                r = padre[r][it].first;
            }
        }
        cout << r+1 << "\n";
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40