oj.uz

Submission #844186

# Submission time Handle Problem Language Result Execution time Memory
844186 2023-09-05T10:52:20 Z _Knyaz_ Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 2752 KB 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long N, Q; cin >> N >> Q;
    vector<pair<long long, long long>> Fountain;
    for(int i = 0; i < N; i++){
        long long Di, Ci; cin >> Di >> Ci;
        Fountain.push_back({Di, Ci});
    }
    bool Check = 1;
    for(int i = 1; i < N; i++){
        if(Fountain[i-1].first > Fountain[i].first) Check = 0;
    }
    if(Check){
        reverse(Fountain.begin(), Fountain.end());
        Fountain.push_back({0, 0});
        reverse(Fountain.begin(), Fountain.end());
        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';
        }
        return 0;
    }
    for(int i = 0; i < Q; i++){
        long long Ri, Vi; cin >> Ri >> Vi;
        long long LastD = 0;
        for(int j = Ri-1; j < N; j++){
            if(Ri == N){
                cout << (Vi > Fountain[j].second ? 0 : j) << '\n';
                break;
            }
            if(Fountain[j].first > LastD){
                Vi -= Fountain[j].second;
                LastD = Fountain[j].first;
            }
            if(Vi < 1){
                cout << j + 1 << '\n';
                break;
            }
        }
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 4 ms 472 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 2592 KB Output is correct
2 Correct 293 ms 2752 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 4 ms 472 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 266 ms 2592 KB Output is correct
9 Correct 293 ms 2752 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Execution timed out 1582 ms 1936 KB Time limit exceeded
12 Halted 0 ms 0 KB -