Submission #1082778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082778		TraianDanciu	Sum Zero (RMI20_sumzero)	C++17	61 / 100	507 ms	21184 KiB

sumzero

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

#define MAXN 400000

int v[MAXN + 1], rmq[3][MAXN + 3], p80[3] = {1, 80, 6400};
std::unordered_map<long long, int> mp;

int main() {
  int n, i, j, k, q, st, dr, rez;
  long long sp; // ce cringe ca trb sa fac asta
  
  scanf("%d", &n);
  for(i = 1; i <= n; i++) {
    scanf("%d", &v[i]);
  }
  
  mp[sp = 0] = n + 1;
  rmq[0][n + 1] = rmq[0][n + 2] = n + 2;
  rmq[0][n] = n + 2 - (v[n] == 0);
  mp[sp = v[n]] = n;
  for(i = n - 1; i > 0; i--) {
    sp += v[i];
    rmq[0][i] = rmq[0][i + 1];
    if(mp.count(sp) && mp[sp] < rmq[0][i]) {
      rmq[0][i] = mp[sp];
    }
    mp[sp] = i;
  }
  
  for(i = 1; i < 3; i++) {
    for(j = 1; j <= n + 2; j++) {
      rmq[i][j] = j;
      for(k = 0; k < 80; k++) {
        rmq[i][j] = rmq[i - 1][rmq[i][j]];
      }
    }
  }
  
  scanf("%d", &q);
  while(q--) {
    scanf("%d%d", &st, &dr);
    rez = 0;
    for(i = 2; i >= 0; i--) {
      while(rmq[i][st] <= dr + 1) {
        st = rmq[i][st];
        rez += p80[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("%d", &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