oj.uz

Submission #653232

# Submission time Handle Problem Language Result Execution time Memory
653232 2022-10-26T09:11:11 Z Blagoj Fountain (eJOI20_fountain) C++14
30 / 100
 16 ms 3404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define endl '\n';

int seg[131100];
int d[100002], c[100002];
pair<int, int> f[100002][20];

void build(int k, int l, int r)
{
    if (l == r)
    {
        seg[k] = d[l];
        return;
    }
    build(k * 2, l, (l + r) / 2);
    build(k * 2 + 1, (l + r) / 2 + 1, r);
    seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
}

int ans = INT_MAX;

void search(int k, int l, int r, int i, int j, int v)
{
    if (l > j || r < i)
    {
        return;
    }
    if (l == r && d[l] > v)
    {
        ans = min(ans, l);
        return;
    }
    if (i <= l && r <= j)
    {
        if (seg[k * 2] > v)
        {
            search(k * 2, l, (l + r) / 2, i, j, v);
        }
        else
        {
            if (seg[k * 2 + 1] > v)
            {
                search(k * 2 + 1, (l + r) / 2 + 1, r, i, j, v);
            }
        }
        return;
    }
    search(k * 2, l, (l + r) / 2, i, j, v);
    search(k * 2 + 1, (l + r) / 2 + 1, r, i, j, v);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> d[i] >> c[i];
    }

    build(1, 1, n);
    f[n][0].second = c[n];
   
    for (int i = n - 1; i >= 1; i--)
    {
        ans = INT_MAX;
        search(1, 1, n, i + 1, n, d[i]);
        if (ans == INT_MAX)
        {
            ans = 0;
        }
        f[i][0].first = ans;
        f[i][0].second = c[i];
    }
    
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = 1; j < 20; j++)
        {
            f[i][j].first = f[f[i][j - 1].first][j - 1].first;
            f[i][j].second = f[f[i][j - 1].first][j - 1].second + f[i][j - 1].second;
        }
    }

    while (q--)
    {
        int r, v;
        cin >> r >> v;
        while (v > 0 && r != 0)
        {
            bool change = false;
            for (int j = 19; j >= 0; j--)
            {
                if (v - (f[r][j].second + 1) >= 0)
                {
                    v -= f[r][j].second;
                    r = f[r][j].first;
                    change = true;
                    break;
                }
            }
            if (!change)
            {
                break;
            }
        }
        cout << r << endl;
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 496 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 3404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 472 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 496 KB Output is correct
8 Runtime error 16 ms 3404 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -