oj.uz

Submission #932617

# Submission time Handle Problem Language Result Execution time Memory
932617 2024-02-24T00:26:32 Z stefanneagu Fountain (eJOI20_fountain) C++17
100 / 100
 728 ms 22812 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 3 ms 4652 KB Output is correct
5 Correct 5 ms 4668 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 21092 KB Output is correct
2 Correct 527 ms 21328 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 3 ms 4444 KB Output is correct
4 Correct 3 ms 4652 KB Output is correct
5 Correct 5 ms 4668 KB Output is correct
6 Correct 5 ms 4444 KB Output is correct
7 Correct 5 ms 4444 KB Output is correct
8 Correct 459 ms 21092 KB Output is correct
9 Correct 527 ms 21328 KB Output is correct
10 Correct 4 ms 4444 KB Output is correct
11 Correct 273 ms 17488 KB Output is correct
12 Correct 728 ms 22812 KB Output is correct
13 Correct 632 ms 22580 KB Output is correct
14 Correct 395 ms 21584 KB Output is correct
15 Correct 376 ms 22468 KB Output is correct