Submission #1223360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223360		khome	Fountain (eJOI20_fountain)	C++20	30 / 100	426 ms	589824 KiB

fountain

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

void solve(){
    int n, q; cin >> n >> q;
    vector<pair<int, int>> vp(n+1); // diametr & capacity
    vector<vector<int>> prefs(n+1); 
    vector<vector<int>> indx(n+1); 
    for (int i = 1; i <= n; i++) {
        cin >> vp[i].first >> vp[i].second;
    }
    for (int i = 1; i <= n; i++) {
        int p = -1, csum = 0;
        for (int j = i; j <= n; j++) {
            if (vp[j].first > p) {
                csum += vp[j].second;
                prefs[i].push_back(csum);
                indx[i].push_back(j);
                p = vp[j].first;
            }
        }
        prefs[i].push_back(1e9);
        indx[i].push_back(0);
    }

    for (int i = 0; i < q; i++){
        int ri, vi; cin >> ri >> vi;
        auto j = lower_bound(prefs[ri].begin(), prefs[ri].end(), vi);
        int x = distance(prefs[ri].begin(), j);
        cout << indx[ri][x] << endl;
    }
}


signed main() {
    ios_base::sync_with_stdio(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
	int t = 1; 
    // cin >> t;
    while (t--){solve();}
}

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