oj.uz

Submission #1070875

# Submission time Handle Problem Language Result Execution time Memory
1070875 2024-08-22T20:17:35 Z matthew Fountain (eJOI20_fountain) C++17
100 / 100
 361 ms 20748 KB 
#include <stdio.h>

const int MAXN = 100'000;
const int MAX_LOG = 17;

int diameter[MAXN + 1], capacity[MAXN + 1];

int sum[MAX_LOG + 1][MAXN + 1];
int next_pos[MAX_LOG + 1][MAXN + 1];

int stiva[MAXN];

int getSum(int pos, int adv) {
  int res = capacity[pos], cnt = 0;
  while(adv > 0) {
    if(adv & 1) {
      res += sum[cnt][pos];
      pos = next_pos[cnt][pos];
    }
    cnt++;
    adv >>= 1;
  }
  return res;
}

int getPos(int pos, int adv) {
  int cnt = 0;
  while(adv > 0) {
    if(adv & 1) {
      pos = next_pos[cnt][pos];
    }
    cnt++;
    adv >>= 1;
  }
  return pos;
}

int main() {
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif

  int n, q, i, j, sp, r, v, st, dr, mij;

  scanf("%d%d", &n, &q);
  for(i = 1; i <= n; i++) {
    scanf("%d%d", &diameter[i], &capacity[i]);
  }

  // pentru fiecare pozitie vreau sa aflu prima pozitie din dreapta
  // pt care diameter[j] > diameter[i]
  // deci fac stiva
  sp = 0;
  for(i = n; i >= 1; i--) {
    while(sp > 0 && diameter[stiva[sp - 1]] <= diameter[i]) {
      sp--;
    }

    if(sp > 0) {
      sum[0][i] = capacity[stiva[sp - 1]];
      next_pos[0][i] = stiva[sp - 1];
    } else {
      sum[0][i] = 0;
      next_pos[0][i] = 0;
    }

    stiva[sp] = i;
    sp++;
  }

  for(i = 1; i <= MAX_LOG; i++) {
    sum[i][0] = 0;
    next_pos[i][0] = 0;
    for(j = 1; j <= n; j++) {
      sum[i][j] = sum[i - 1][j] + sum[i - 1][next_pos[i - 1][j]];
      next_pos[i][j] = next_pos[i - 1][next_pos[i - 1][j]];
    }
  }

  for(i = 0; i < q; i++) {
    scanf("%d%d", &r, &v);
    
    st = -1;
    dr = n - 1;
    while(dr - st > 1) {
      mij = (st + dr) / 2;
      if(v <= getSum(r, mij)) {
        dr = mij;
      } else {
        st = mij;
      }
    }


    printf("%d\n", (v > getSum(r, dr)) ? 0 : getPos(r, dr));
  }

  return 0;
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d%d", &n, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~
fountain.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d%d", &diameter[i], &capacity[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     scanf("%d%d", &r, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 19028 KB Output is correct
2 Correct 252 ms 19072 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 12636 KB Output is correct
4 Correct 3 ms 12636 KB Output is correct
5 Correct 2 ms 12636 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 2 ms 12636 KB Output is correct
8 Correct 236 ms 19028 KB Output is correct
9 Correct 252 ms 19072 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 118 ms 16212 KB Output is correct
12 Correct 361 ms 20748 KB Output is correct
13 Correct 319 ms 20332 KB Output is correct
14 Correct 139 ms 19280 KB Output is correct
15 Correct 92 ms 19540 KB Output is correct