제출 #932617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
932617		stefanneagu	Fountain (eJOI20_fountain)	C++17	100 / 100	728 ms	22812 KiB

fountain

#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5 + 1;

int w[nmax], l[nmax], ng[nmax], sz[nmax], v[nmax];
int su[nmax][20], nu[nmax][20];

void nextg(int n) {
  stack<int> s;
  for(int i = 1; i <= n; i ++) {
    if(!s.size()) {
      s.push(i);
      continue;
    }
    while(!s.empty() && v[s.top()] < v[i]) {
      ng[s.top()] = i;
      s.pop();
    }
    s.push(i);
  }
  while(!s.empty()) {
    ng[s.top()] = 0;
    s.pop();
  }
}

int sum(int n, int x) {
  int sum = 0;
  for(int bit = 0; bit < 20; bit ++) {
    if(x & (1 << bit)) {
      sum += su[n][bit];
      n = nu[n][bit];
    }
  }
  return sum;
}

int up(int n, int x) {
  for(int bit = 0; bit < 20; bit ++) {
    if(x & (1 << bit)) {
      n = nu[n][bit];
    }
  }
  return n;
}

int main() {
  int n, q;
  cin >> n >> q;
  for(int i = 1; i <= n; i ++) {
    cin >> v[i] >> w[i];
  }
  nextg(n);
  for(int i = n; i >= 1; i --) {
    sz[i] = sz[ng[i]] + 1;
    nu[i][0] = ng[i];
    su[i][0] = w[ng[i]];
    // cout << i << " 1: " << nu[i][0] <<  " " << su[i][0] << '\n';
  }
  for(int j = 1; (1 << j) <= n; j ++) {
    for(int i = 1; i <= n; i ++) {
      if((1 << j) >= sz[i]) {
        continue;
      }
      nu[i][j] = nu[nu[i][j - 1]][j - 1];
      su[i][j] = su[i][j - 1] + su[nu[i][j - 1]][j - 1];
      // cout << i << " " << (1 << j) << ": " << nu[i][j] << ' ' << su[i][j] << '\n';
    }
  }
  while(q --) {
    int a, b;
    cin >> a >> b;
    b -= w[a];
    if(b <= 0) {
      cout << a << '\n';
      continue;
    }
    int l = 0, r = sz[a] - 1, ans = -1;
    while(l <= r) {
      int mid = (l + r) / 2;
      if(sum(a, mid) >= b) {
        ans = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    if(ans == -1) {
      cout << "0\n";
      continue;
    }
    cout << up(a, ans) << '\n';
  }
  return 0;
}

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