oj.uz

Submission #467491

# Submission time Handle Problem Language Result Execution time Memory
467491 2021-08-23T09:12:11 Z myvaluska Fountain (eJOI20_fountain) C++14
0 / 100
 503 ms 32700 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 28216 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 503 ms 32700 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 28216 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -