oj.uz

Submission #1020285

# Submission time Handle Problem Language Result Execution time Memory
1020285 2024-07-11T19:36:31 Z FIFI_cpp Fountain (eJOI20_fountain) C++17
30 / 100
 1500 ms 9252 KB 
#include <iostream>
#include <vector>
#include <stack>
using ll = int64_t;
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

const int INF = 10000000000000000;
const int mod = 1000000007;

int32_t main() {
    fast
    int n, q;
    cin >> n >> q;

    vector<pair<int, int>> a(n, {-1, -1});
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second; // diameter, volume
    }

    vector<vector<pair<int, int>>> query(n);
    vector<int> res(q, 0);
    for (int i = 0; i < q; i++) {
        int r, v;
        cin >> r >> v;
        r--;
        query[r].pb({i, v});
    }

    stack<pair<pair<int, int>, int>> st; // quantity, radius, query
    for (int i = 0; i < n; i++) {
        stack<pair<pair<int, int>, int>> curr;
        while (!st.empty() && a[i].first > st.top().first.second) {
            auto [q, qu] = st.top();
            if (q.first - a[i].second > 0) {
                curr.push({{q.first - a[i].second, a[i].first}, qu});
            } else {
                res[qu] = i + 1;
            }
            st.pop();
        }

        while (!curr.empty()) {
            st.push(curr.top());
            curr.pop();
        }

        for (auto& [index, v] : query[i]) {
            if (a[i].second >= v) {
                res[index] = i + 1;
            } else {
                st.push({{v - a[i].second, a[i].first}, index});
            }
        }
    }

    for (int i = 0; i < q; i++) {
        cout << res[i] << '\n';
    }

    return 0;
}

Compilation message

fountain.cpp:10:17: warning: overflow in conversion from 'long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
   10 | const int INF = 10000000000000000;
      |                 ^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1565 ms 9252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Execution timed out 1565 ms 9252 KB Time limit exceeded
9 Halted 0 ms 0 KB -