Submission #432857

#	Time	Username	Problem	Language	Result	Execution time	Memory
432857		Valaki2	Fountain (eJOI20_fountain)	C++14	60 / 100	92 ms	5188 KiB

fountain

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

int n, q;

// brute force
void solve1() {
    vector<int> width(1 + n, 0);
    vector<int> capacity(1 + n, 0);
    for(int i = 1; i <= n; ++i) {
        cin >> width[i] >> capacity[i];
    }
    
    while(q--) {
        int s, cur;
        cin >> s >> cur;
        int last_width = width[s];
        cur -= capacity[s];
        if(cur <= 0) {
            cout << s << "\n";
            continue;
        }
        while(s <= n) {
            if(width[s] > last_width) {
                last_width = width[s];
                cur -= capacity[s];
                if(cur <= 0) {
                    cout << s << "\n";
                    break;
                }
            }
            ++s;
        }
        if(s == n + 1) {
            cout << "0\n";
        }
    }
}

// strictly increasing
void solve2() {
    vector<int> width(1 + n, 0);
    vector<int> capacity(1 + n, 0);
    vector<int> prefix_capacity(1 + n, 0);
    for(int i = 1; i <= n; ++i) {
        cin >> width[i] >> capacity[i];
        prefix_capacity[i] = prefix_capacity[i - 1] + capacity[i];
        // cout << prefix_capacity[i] << " ";
    }
    // cout << "\n";
    while(q--) {
        int s, amount;
        cin >> s >> amount;
        if(prefix_capacity[s] - capacity[s] + amount > prefix_capacity[n]) {
            cout << "0\n";
            continue;
        }
        auto it = lower_bound(prefix_capacity.begin(), prefix_capacity.end(), prefix_capacity[s] - capacity[s] + amount);
        cout << (int) (it - prefix_capacity.begin()) << "\n";
    }
}

void solve() {
    cin >> n >> q;
    if(n <= 1000 && q <= 2000) {
        solve1();
    } else {
        solve2();
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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