제출 #1309132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309132		ayaz	Fountain (eJOI20_fountain)	C++20	100 / 100	524 ms	38520 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())
#define int ll

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, LOG = 30;
const ll mod = 1000000007, INF = 1000000000000000000;

int d[sz], c[sz], nxt[sz];
int par[sz][LOG], sm[sz], dep[sz];
vi g[sz];

void dfs(int u, int p) {
  sm[u] += sm[p];
  par[u][0] = p;
  dep[u] = dep[p] + 1;
  for (auto &v : g[u]) {
    dfs(v, u);
  }
}
void precompute() {}
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] = n+1;
    sm[i] = c[i];
  }
  stack<int> st;
  st.push(n + 1);
  d[n + 1] = inf;
  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);
  }
  for (int i = 1; i <= n; i++) {
    g[nxt[i]].push_back(i);
  }
  dfs(n + 1, 0);
  for (int d = 1; d < LOG; d++)
    for (int u = 1; u <= n; u++)
      par[u][d] = par[par[u][d - 1]][d - 1]; 
  while (q--) {
    int r, v; cin >> r >> v;
    int low = 0, high = dep[r];
    int best = 0;

    auto check = [&](int m) -> bool {
      int u = r;
      for (int i = 0; i < LOG; i++)
        if (m >> i & 1)
          u = par[u][i];
      return (sm[r] - sm[u] + c[u] >= v);
    };

    while (low <= high) {
      int mid = (low + high) >> 1;
      if (check(mid)) {
        high = mid - 1;
        best = mid;
      } else {
        low = mid + 1;
      }
    }

    int sum = sm[r];
    for (int i = 0; i < LOG; i++)
      if (best >> i & 1)
        r = par[r][i];
    sum -= sm[r];
    sum += c[r];
    cout << (sum < v ? 0 : r) << '\n';
  }
}

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