Submission #1020285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020285		FIFI_cpp	Fountain (eJOI20_fountain)	C++17	30 / 100	1565 ms	9252 KiB

fountain

#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 (stderr)

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 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40