Submission #432840

#	Time	Username	Problem	Language	Result	Execution time	Memory
432840		Valaki2	Fountain (eJOI20_fountain)	C++14	30 / 100	4 ms	332 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() {
    
}

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: 0 / 30
• Subtask 3: 0 / 40