Submission #1219673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219673		hiderr	Fountain (eJOI20_fountain)	C++20	100 / 100	82 ms	13140 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

#define loop(i, a, b) for(int i = a; i <= b; i++)
#define loop_rev(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define pb push_back

using ll = long long;

struct StackEntry {
    int d;
    ll sum;
    int ind;
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q; cin >> n >> q;

  vector<int> d(n + 1), c(n + 1);

  loop(i, 1, n) {
    cin >> d[i] >> c[i];
  }

  d[0] = 2e9;

  vector<vector<pair<int, ll>>> que(n + 1);

  loop(i, 0, q - 1) {
    int ind, v; cin >> ind >> v;
    que[ind].pb({ v, i });
  }

  vector<int> res(q);
  vector<StackEntry> st;
  st.pb({ d[0], c[0], 0 });

  loop_rev(i, n, 1) {
    while(st.back().d <= d[i]) {
        st.pop_back();
    }
    st.push_back({ d[i], c[i] + st.back().sum, i });
    for(auto [ val, q_ind ] : que[i]) {
        int l = -1, r = sz(st) - 2;
        while(l < r) {
            int mid = (l + r + 1) / 2;
            if(st.back().sum - st[mid].sum >= val) {
                l = mid;
            }
            else {
                r = mid - 1;
            }
        }
        res[q_ind] = st[l + 1].ind;
    }
  }

  loop(i, 0, q-1) {
    cout << res[i] << '\n';
  }

}

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