제출 #456299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
456299		myvaluska	Fountain (eJOI20_fountain)	C++14	60 / 100	437 ms	5560 KiB

fountain

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <cmath>
#include <tuple>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
/*long long int power(long long int n, int k)
{
    long long int vys = 1;
    for (int i = 0; i < k; i++)
    {
        vys = (vys * (n - i)) / (i + 1);
    }
    return vys;
}*/
const int inf = 1000000037;
int main()
{
    /*for (int i = 0; i < 10; i++)
    {
        std::cout << "Hello Flash!\n";
    }*/

    //cout << "TU" << endl;
    int n;
    int q;
    cin >> n;
    cin >> q;
    vector<int>priemer(n);
    vector<int>objem(n);
    for (int i = 0; i < n; i++)
    {
        cin >> priemer[i];
        cin >> objem[i];
    }
    priemer.push_back(inf);
    objem.push_back(inf);
    if (n <= 1000 && q <= 2000)
    {
        while (q--)
        {
            int u;
            int v;
            cin >> u;
            cin >> v;
            u -= 1;
            int p = priemer[u];
            v -= objem[u];
            if (v <=0)
            {
                cout << u + 1 << endl;
            }
            else
            {
                for (int i = u+1; i < n+1; i++)
                {
                    if (priemer[i] > p)
                    {
                        p = priemer[i];
                        v -= objem[i];
                    }
                    if (v <=0)
                    {
                        if (i == n)
                        {
                            cout << 0 << endl;
                        }
                        else
                        {
                            cout << i + 1 << endl;
                        }
                        break;
                    }

                }
            }
            

        }
    }
    else
    {
        vector<long long int>prefix(n+1);
        prefix[0] = objem[0];
        for (int i = 1; i < n+1; i++)
        {
            prefix[i] = prefix[i - 1] + objem[i];
        }
        while (q--)
        {
            int u;
            int v;
            cin >> u;
            cin >> v;
            u -= 1;
            if (u > 0)
            {
                v += prefix[u - 1];
            }
            int index = lower_bound(prefix.begin() + u, prefix.end(),v) - prefix.begin();
            if (index == n)
            {
                cout << 0 << endl;
            }
            else
            {
                cout << index+1 << endl;
            }
        }
    }
    return 0;
}

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