Submission #771219

#	Time	Username	Problem	Language	Result	Execution time	Memory
771219		cnastea	Fountain (eJOI20_fountain)	C++14	60 / 100	268 ms	4848 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> d(n+1), c(n);
    d[n] = 1000000001;
    for(int i = 0; i < n; i++){
        cin >> d[i] >> c[i];
    }
    if(n <= 1000 && q <= 2000){
        int r, v;
        for(int i = 0; i < q; i++){
            cin >> r >> v;
            int k = r-1, m = r-1;
            v -= c[m];
            while(v > 0 && m <= n && k < n){
                if(d[m] > d[k]){
                    v -= c[m];
                    k = m;
                }
                m++;
            }
            if(k == n) cout << 0 << "\n";
            else cout << k+1 << "\n";
        }
    }
    else{
        for(int i = n-2; i >= 0; i--){
            c[i] += c[i+1];
        }
        for(int i = 0; i < q; i++){
            int r, v;
            cin >> r >> v;
            if(c[r-1]-v >= 0 && c[r-1]-v < c[n-1]) cout << n << "\n";
            else if(c[r-1]-v < 0) cout << 0 << "\n";
            else{
                int a = 0, b = n;
                while(b - a > 1){
                    int m = (a+b)/2;
                    if(c[r-1]-v < c[m]) a = m;
                    else b = m;
                }
                cout << b << "\n";
            }
        }
    }
    return 0;
}

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