Submission #1070875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070875		matthew	Fountain (eJOI20_fountain)	C++17	100 / 100	361 ms	20748 KiB

fountain

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40