제출 #1309066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309066		ayaz	Fountain (eJOI20_fountain)	C++20	60 / 100	1609 ms	267200 KiB

fountain

// We were born for this
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#define line() "author : AyazN";
#endif

typedef long long ll;

#define all(x) (x).begin(), (x).end()
#define isz(x) (int)(x.size())

typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int sz = 200500, inf = 1000000000;
const ll mod = 1000000007, INF = 1000000000000000000;

void precompute() {}
int d[sz], c[sz], nxt[sz];
int id[sz], idx_id[sz]; // in which level is idx
vpii lvl[sz];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef LOCAL
  freopen("err.log", "w", stderr);
#endif
  precompute();
  int n, q;
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> d[i] >> c[i];
    nxt[i] = inf;
  }
  d[n + 1] = inf;
  stack<int> st;
  st.push(n + 1);
  for (int i = n; i >= 1; i--) {
    while (!st.empty() && d[st.top()] <= d[i]) st.pop();
    if (!st.empty()) nxt[i] = st.top();
    st.push(i);
  }
  int l = 0;
  set<int> idx;
  for (int i = 1; i <= n; i++) {
    idx.insert(i);
  }
  while (!idx.empty()) {
    lvl[l].push_back({0, 0});
    int st = *idx.begin();
    while (st != n + 1) {
      idx_id[st] = isz(lvl[l]);
      lvl[l].push_back({lvl[l].back().first + c[st], st});      
      id[st] = l;
      auto it = idx.find(st);
      if (it != idx.end()) 
        idx.erase(it);
      st = nxt[st];
    }
    l++;
  }
  while (q--) {
    int r, v;
    cin >> r >> v;
    int i = id[r], idx = idx_id[r];
    int low = 1, high = isz(lvl[i]) - 1, best = 0;
    auto check = [&](int mid) -> bool {
      return (lvl[i][mid].first - lvl[i][idx - 1].first >= v);
    };
    while (low <= high) {
      int mid = (low + high) >> 1;
      if (check(mid)) {
        high = mid - 1;
        best = mid;
      } else {
        low = mid + 1;
      }
    }
    cout << lvl[i][best].second << '\n';
  }
}

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