Submission #1110422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110422		TraianDanciu	Sum Zero (RMI20_sumzero)	C++17	61 / 100	415 ms	20504 KiB

sumzero

// Calcul pt ce puteri folosim la rmq:
// v ~ 8*4e5; poz ~ 4*4e5
// total: 20*1024*1024 - 4e5*(4+8) = 16171520
// cate randuri putem folosi: 16171520/4e5/4 ~ 10
// 2^10 < 4e5; 3^10 < 4e5; 4^10 > 4e5 -> rmq pe puteri de 4
// Pot sa scap de vectorul ultim (ce tryhard)
// Complexitatea de timp e O((n + q) * NUM_LEVELS * BASE)
// In cel mai rau caz ar trebui cam vreo 10^8 operatii
// 10^8/8e5 = 10^3/8 = 125 deci NUM_LEVELS * BASE <= 125
// NUM_LEVELS scade cand BASE creste; BASE <= 30
// Sa vedem ce se intampla cand BASE = 30

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

const int MAXN = 400'000;
const int BASE = 30;
const int NUM_LEVELS = 4;

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

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++) {
    poz[i] = n + 1;
  }
  spt[0][n + 1] = n + 1;
  for(i = n; i >= 0; i--) {
    spt[0][i] = min(spt[0][i + 1], poz[v[i]]);
    poz[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:26:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
sumzero.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%lld", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~~~
sumzero.cpp: In function 'void processQueries()':
sumzero.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
sumzero.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     scanf("%d%d", &st, &dr);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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