Submission #1110413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110413		TraianDanciu	Sum Zero (RMI20_sumzero)	C++17	61 / 100	256 ms	27208 KiB

sumzero

// Calcul pt ce puteri folosim la rmq:
// v ~ 8*4e5; poz ~ 4*4e5; ultim ~ 4*4e5
// total: 20*1024*1024 - 4e5*(4+4+8) = 16171520
// cate randuri putem folosi: 14571520/4e5/4 ~ 0
// 2^0 < 4e5; 3^9 < 4e5; 4^9 < 4e5; 5^9 > 4e5; -> rmq pe puteri de 5
// hm imi iau mle cu puteri de 5 asa ca o sa incerc cu puteri de 6

#include <stdio.h>
#include <algorithm>

const int MAXN = 400'000;
const int BASE = 6;
const int NUM_LEVELS = 8;

long long v[MAXN + 1];
int n, poz[MAXN + 1], norm0;
int spt[NUM_LEVELS][MAXN + 2], powers[NUM_LEVELS], ultim[MAXN + 1];

void readArray() {
  int i;
  scanf("%d", &n);
  for(i = 1; i <= n; i++) {
    scanf("%lld", &v[i]);
  }
}

void computePrefixSums() {
  int i;
  for(i = 1; i <= n; i++) {
    v[i] += v[i - 1];
  }
}

void normalizeArray() {
  int i, cnt;
  long long prev;
  
  for(i = 0; i <= n; i++) {
    poz[i] = i;
  }
  std::sort(poz, poz + n + 1, [](int a, int b) {
    return v[a] < v[b];
  });
  
  prev = v[poz[0]]; // ca sa nu mai creez inca un vector
  v[poz[0]] = cnt = 0;
  for(i = 1; i <= n; i++) {
    if(v[poz[i]] > prev) {
      if(v[poz[i]] == 0) {
        norm0 = cnt;
      }
      cnt++;
    }
    prev = v[poz[i]];
    v[poz[i]] = cnt;
  }
}

int min(int a, int b) {
  return a < b ? a : b;
}

void computeSparseTable() {
  int i, j, p;
  
  for(i = 0; i <= n; i++) {
    ultim[i] = n + 1;
  }
  spt[0][n + 1] = n + 1;
  for(i = n; i >= 0; i--) {
    spt[0][i] = min(spt[0][i + 1], ultim[v[i]]);
    ultim[v[i]] = i;
  }
  
  powers[0] = 1;
  for(i = 1; i < NUM_LEVELS; i++) {
    for(j = 0; j <= n + 1; j++) {
      spt[i][j] = j;
      for(p = 0; p < BASE; p++) {
        spt[i][j] = spt[i - 1][spt[i][j]];
      }
    }
    
    powers[i] = powers[i - 1] * BASE;
  }
}

void processQueries() {
  int q, st, dr, i, answer;
  scanf("%d", &q);
  while(q--) {
    scanf("%d%d", &st, &dr);
    answer = 0;
    st--;
    for(i = NUM_LEVELS - 1; i >= 0; i--) {
      while(spt[i][st] <= dr) {
        answer += powers[i];
        st = spt[i][st];
      }
    }
    printf("%d\n", answer);
  }
}

int main() {
  readArray();
  computePrefixSums();
  normalizeArray();
  computeSparseTable();
  processQueries();
  return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'void readArray()':
sumzero.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
sumzero.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%lld", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
sumzero.cpp: In function 'void processQueries()':
sumzero.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
sumzero.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     scanf("%d%d", &st, &dr);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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