Submission #770707

#	Time	Username	Problem	Language	Result	Execution time	Memory
770707		cnastea	Fountain (eJOI20_fountain)	C++14	30 / 100	1556 ms	323180 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){
        for(int i = 0; i < q; i++){
            int r, v;
            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];
        }
        map<int, int> m;
        int k = n-1;
        for(int i = 0; i <= c[0]; i++){
            if(k > 0 && c[k] <= i){
                k--;
            }
            m[i] = k+1;
        }
        for(int i = 0; i < q; i++){
            int r, v;
            cin >> r >> v;
            if(m[c[r-1]-v] == n+1) cout << 0 << "\n";
            else cout << m[c[r-1]-v] << "\n";
        }
    }
    return 0;
}

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