oj.uz

Submission #1069251

# Submission time Handle Problem Language Result Execution time Memory
1069251 2024-08-21T18:09:18 Z raduv Fountain (eJOI20_fountain) C++14
100 / 100
 114 ms 17236 KB 
  #include <stdio.h>
  #include <utility>
  #include <ctype.h>
  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 8536 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 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 73 ms 15428 KB Output is correct
2 Correct 84 ms 14468 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 0 ms 2652 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 73 ms 15428 KB Output is correct
9 Correct 84 ms 14468 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 38 ms 10228 KB Output is correct
12 Correct 114 ms 16432 KB Output is correct
13 Correct 92 ms 16464 KB Output is correct
14 Correct 44 ms 16212 KB Output is correct
15 Correct 35 ms 17236 KB Output is correct