Submission #844178

#	Time	Username	Problem	Language	Result	Execution time	Memory
844178		_Knyaz_	Fountain (eJOI20_fountain)	C++17	30 / 100	309 ms	5748 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long N, Q; cin >> N >> Q;
    vector<pair<long long, long long>> Fountain = {{0, 0}};
    for(int i = 0; i < N; i++){
        long long Di, Ci; cin >> Di >> Ci;
        Fountain.push_back({Di, Ci});
    }
    for(int i = 1; i <= N; i++){
        Fountain[i].second += Fountain[i-1].second;
    }
    for(int i = 0; i < Q; i++){
        long long Ri, Vi; cin >> Ri >> Vi;
        int L = Ri - 1, R = N;
        if(Vi > Fountain[N].second){
            cout << 0 << '\n';
            break;
        }
        while(L <= R){
            long long Mid = (L + R) / 2;
            if(Fountain[Mid].second - Fountain[Ri-1].second == Vi){
                R = Mid - 1; L = Mid;
            }
            else if(Fountain[Mid].second - Fountain[Ri-1].second > Vi){
                R = Mid - 1;
            }
            else{
                L = Mid + 1;
            }
        }
        cout << L << '\n';
    }
}

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