제출 #467491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467491		myvaluska	Fountain (eJOI20_fountain)	C++14	0 / 100	503 ms	32700 KiB

fountain

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn = 100037;
const int logn = 17;
const int inf = 1000000037;
vector<vector<int>>p(logn,vector<int>(maxn,0));
vector<vector<int>>suc(logn, vector<int>(maxn, inf));
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    int q;
    cin >> n;
    cin >> q;
    vector<int>d(n + 2);
    vector<int>c(n + 2);
    vector<int>r(n + 2);
    vector<int>v(n + 2);
    d[0] = inf;
    c[0] = inf;
    for (int i = 1; i < n + 1; i++)
    {
        cin >> d[i];
        cin >> c[i];
    }
    vector<int>stk;
    stk.push_back(0);
    for (int i = n; i >= 1; i--)
    {
        while (d[stk.back()] <= d[i])
        {
            stk.pop_back();
        }
        p[0][i] = stk.back();
        suc[0][i] = c[stk.back()];
        stk.push_back(i);
    }
    for (int i = 1; i < logn; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            p[i][j] = p[i - 1][p[i - 1][j]];
            suc[i][j] = min(suc[i - 1][j] + suc[i - 1][p[i - 1][j]], inf);
        }
    }
    for (int i = 0; i < q; i++)
    {
        cin >> r[i];
        cin >> v[i];
        int vr = r[i];
        if (c[r[i]] >= v[i])
        {
            cout << r[i] << endl;
        }
        else
        {
            v[i] -= c[r[i]];
            for (int j = logn - 1; j >= 0; j--)
            {
                if (suc[j][vr] < v[i])
                {
                    v[i] -= suc[j][vr];
                    vr = p[j][vr];
                }
            }
            vr = p[0][vr];
            cout << vr << endl;
        }
    }
    return 0;
}

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