제출 #1110323

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110323		TraianDanciu	Sum Zero (RMI20_sumzero)	C++17	61 / 100	405 ms	23792 KiB

sumzero

#include <stdio.h>
#include <algorithm>
 
#define MAXN 400000
#define INFINIT 1000000000000000000LL
 
int v[MAXN + 1], rmq[3][MAXN + 3], p50[3] = {1, 50, 2500}, vf[MAXN + 1];

struct Element {
  long long val;
  int poz;
} w[MAXN + 1];

int main() {
  int n, i, j, k, q, st, dr, rez, cnt, zero, m;
  long long sp;
  
  scanf("%d", &n);
  for(i = 1; i <= n; i++) {
    scanf("%d", &v[i]);
    w[i].poz = i;
  }
  
  w[n].val = sp = v[n];
  w[0].val = w[0].poz = 0;
  zero = (v[n] == 0);
  for(i = n - 1; i > 0; i--) {
    sp += v[i];
    w[i].val = sp;
  }
  std::sort(w, w + n + 1, [](Element a, Element b) {
    return a.val < b.val;
  });
  v[w[0].poz] = cnt = 0;
  for(i = 1; i <= n; i++) {
    if(w[i].val > w[i - 1].val) {
      cnt++;
    }
    v[w[i].poz] = cnt;
  }
  
  vf[v[0]] = n + 1;
  vf[v[n]] = n;
  rmq[0][n + 1] = rmq[0][n + 2] = n + 2;
  rmq[0][n] = n + 2 - zero;
  for(i = n - 1; i > 0; i--) {
    rmq[0][i] = rmq[0][i + 1];
    if(vf[v[i]] != 0 && vf[v[i]] < rmq[0][i]) {
      rmq[0][i] = vf[v[i]];
    }
    vf[v[i]] = i;
  }
  
  for(i = 1; i < 3; i++) {
    for(j = 1; j <= n + 2; j++) {
      rmq[i][j] = j;
      for(k = 0; k < 50; 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 += p50[i];
      }
    }
    printf("%d\n", rez);
  }
  
  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sumzero.cpp: In function 'int main()':
sumzero.cpp:15:46: warning: unused variable 'm' [-Wunused-variable]
   15 |   int n, i, j, k, q, st, dr, rez, cnt, zero, m;
      |                                              ^
sumzero.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
sumzero.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~
sumzero.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d", &q);
      |   ~~~~~^~~~~~~~~~
sumzero.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d%d", &st, &dr);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

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