Submission #1082774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082774		TraianDanciu	Sum Zero (RMI20_sumzero)	C++17	61 / 100	359 ms	24528 KiB

sumzero

#include <stdio.h>
#include <unordered_map>

#define MAXN 400000

long long v[MAXN + 1];
int rmq[4][MAXN + 3], p30[4] = {1, 30, 900, 27000};
std::unordered_map<long long, int> mp;

int main() {
  int n, i, j, k, q, st, dr, rez;
  
  scanf("%d", &n);
  for(i = 1; i <= n; i++) {
    scanf("%lld", &v[i]);
  }
  
  mp[0] = n + 1;
  rmq[0][n + 1] = rmq[0][n + 2] = n + 2;
  rmq[0][n] = n + 2 - (v[n] == 0);
  mp[v[n]] = n;
  for(i = n - 1; i > 0; i--) {
    v[i] += v[i + 1];
    rmq[0][i] = rmq[0][i + 1];
    if(mp.count(v[i]) && mp[v[i]] < rmq[0][i]) {
      rmq[0][i] = mp[v[i]];
    }
    mp[v[i]] = i;
  }
  
  for(i = 1; i < 4; i++) {
    for(j = 1; j <= n + 2; j++) {
      rmq[i][j] = j;
      for(k = 0; k < 30; k++) {
        rmq[i][j] = rmq[i - 1][rmq[i][j]];
      }
    }
  }
  
  scanf("%d", &q);
  while(q--) {
    scanf("%d%d", &st, &dr);
    rez = 0;
    for(i = 3; i >= 0; i--) {
      while(rmq[i][st] <= dr + 1) {
        st = rmq[i][st];
        rez += p30[i];
      }
    }
    printf("%d\n", rez);
  }
  
  return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
sumzero.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%lld", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
sumzero.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
sumzero.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d%d", &st, &dr);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 0 / 39