oj.uz

Submission #456299

# Submission time Handle Problem Language Result Execution time Memory
456299 2021-08-06T11:20:24 Z myvaluska Fountain (eJOI20_fountain) C++14
60 / 100
 437 ms 5560 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 4 ms 204 KB Output is correct
5 Correct 6 ms 204 KB Output is correct
6 Correct 6 ms 204 KB Output is correct
7 Correct 5 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 2412 KB Output is correct
2 Correct 437 ms 5560 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 3 ms 204 KB Output is correct
4 Correct 4 ms 204 KB Output is correct
5 Correct 6 ms 204 KB Output is correct
6 Correct 6 ms 204 KB Output is correct
7 Correct 5 ms 204 KB Output is correct
8 Correct 377 ms 2412 KB Output is correct
9 Correct 437 ms 5560 KB Output is correct
10 Incorrect 7 ms 332 KB Output isn't correct
11 Halted 0 ms 0 KB -