oj.uz

Submission #432857

# Submission time Handle Problem Language Result Execution time Memory
432857 2021-06-18T14:19:00 Z Valaki2 Fountain (eJOI20_fountain) C++14
60 / 100
 92 ms 5188 KB 
#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.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 4952 KB Output is correct
2 Correct 92 ms 5188 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 79 ms 4952 KB Output is correct
9 Correct 92 ms 5188 KB Output is correct
10 Incorrect 1 ms 328 KB Output isn't correct
11 Halted 0 ms 0 KB -