oj.uz

Submission #1069247

# Submission time Handle Problem Language Result Execution time Memory
1069247 2024-08-21T18:06:43 Z raduv Fountain (eJOI20_fountain) C++14
100 / 100
 96 ms 17136 KB 
#include <stdio.h>
#include <utility>
#include <ctype.h>
#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#pragma GCC target ("avx2")
const int MAXN = 100'000;
const int LOG = 18;
using namespace std;
int rmq[LOG + 1][MAXN + 1], cap[LOG + 1][MAXN + 1];
pair<int, int> stiva[MAXN + 1];
int ns;
static inline int getInt(){
  int n = 0, ch;
  while(!isdigit(ch = getc(stdin)));
  do
    n = n * 10 + ch - '0';
  while (isdigit(ch = getc(stdin)));
  return n;
}
int main()
{
    int n, q, i, diam, p, a, b;
    n = getInt();
    q = getInt();
    for( i = 1; i <= n; i++ ){
      diam = getInt();
      cap[0][i] = getInt();
      while(ns > 0 && diam > stiva[ns].first)
        rmq[0][stiva[ns--].second] = i;
      stiva[++ns] = {diam, i};
    }
    while(ns > 0)
      rmq[0][stiva[ns--].second] = i;
    for ( p = 1; p <= LOG; p++ ){
      for( i = 1; i <= n; i++ ){
        rmq[p][i] = rmq[p - 1][rmq[p - 1][i]];
        cap[p][i] = cap[p - 1][i] + cap[p - 1][rmq[p - 1][i]];
      }
    }
    while(q--){
      a = getInt();
      b = getInt();
      for( i = LOG; i >= 0; i-- ){
        if(cap[i][a] < b){
          b -= cap[i][a];
          a = rmq[i][a];
        }
      }
      printf("%d\n", a);
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 15700 KB Output is correct
2 Correct 72 ms 15156 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 66 ms 15700 KB Output is correct
9 Correct 72 ms 15156 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 35 ms 12684 KB Output is correct
12 Correct 96 ms 16464 KB Output is correct
13 Correct 84 ms 16512 KB Output is correct
14 Correct 42 ms 16468 KB Output is correct
15 Correct 34 ms 17136 KB Output is correct