Submission #459470

#	Time	Username	Problem	Language	Result	Execution time	Memory
459470		liza	Fountain (eJOI20_fountain)	C++14	30 / 100	1570 ms	3564 KiB

fountain

#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;


int main()
{

    int N, Q, R, V;
    cin >> N >> Q;
    int R1;
    //int N1 = N + 1;

    //int d[N + 2], c[N + 2], m[N + 2];

    //int *d = new int[N+2];
    //int *c = new int[N+2];
    //int *m = new int[N+2];
    //int *cm = new int[N+2];
    int d[N + 2], c[N + 2], m[N + 2], cm[N +2];
    int j;
  //  vector <pair <int, long long>> ma[N + 2];

    d[0] = c[0] = 0;
    d[N + 1] = 1000000001;
    c[N + 1] = 1001;
    cm[N + 1] = m[N +1 ] = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> d[i] >> c[i];
    }

    for (int i = N; i > 0; i--)
    {
        j = i + 1;
        while (true)
        {
            if (d[i] < d[j])
            {
                m[i] = j;
                cm[i] = cm[j] + c[i];
                break;
            }
            j = m[j];
        }
    }
    /*long long cj = 0;
    for (int i = 1; i < N1; i++)
    {
            cout << " " << i << " ";

        j = i;
        cj = c[i];
        while (true)
        {
            ma[i].push_back(make_pair(j, cj));
            //cout << " j:" << j << " cj:" << cj;
            cout <<     " " << j << " ";
            //cin >> a;
            if (j > N)
            {
                cout << "\n";

                break;
            }
            j = m[j];
            cj += c[j];
        }
        //cout << "\n";
    }*/
    //size_t j2;
    for (int i = 0; i < Q; i++)
    {
        cin >> R >> V;
        V = cm[R] - V;
        if (V < 0)
        {
            cout << "0\n";
            continue;
        }
        R1 = R;
        while (R > 0)
        {
            if (cm[R] <= V)
            {
                cout << R1 << "\n";
                break;
            }
            else
            {
                R1 = R;
                R = m[R];
            }
        }
        if (R == 0)
        {
            if (R1 > V)
            {
                cout << "0\n";
            }
            else
            {
                cout << R1 << "\n";
            }

        }
    }

   // delete [] d;
    //delete [] c;
    //delete [] m;

    return 0;
}

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