제출 #942921

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

sumzero

#include <bits/stdc++.h>

#define nl '\n'

#ifdef LOCAL
#include "template\debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  std::vector<int> a(n + 1);
  
  int64_t sum = 0;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    sum += a[i];
  }
  
  std::vector<int> jump(n + 2), depth(n + 2), parent(n + 2);
  jump[n + 1] = n + 1;
  
  std::map<int64_t, int> mp;
  for (int i = n, to = n + 1; i >= 0; i--) {
    auto it = mp.find(sum);
    int right_most;
    if (it == mp.end()) {
      right_most = n + 1;
    } else {
      right_most = it->second;
    }
    mp[sum] = i;
    to = std::min(to, right_most);
    parent[i] = to;
    depth[i] = depth[parent[i]] + 1;
    if (depth[parent[i]] - depth[jump[parent[i]]] == depth[jump[parent[i]]] - depth[jump[jump[parent[i]]]]) {
      jump[i] = jump[jump[parent[i]]];
    } else {
      jump[i] = parent[i];
    }
    sum -= a[i];
  }
  
  int Q;
  std::cin >> Q;
  while (Q--) {
    int l, r;
    std::cin >> l >> r;
    l--;

    int counter = 0;
    int u = l;
    while (parent[u] <= r) {
      if (jump[u] <= r) {
        counter += depth[u] - depth[jump[u]];
        u = jump[u];
      } else {
        counter++;
        u = parent[u];
      }
    }
    
    std::cout << counter << nl;
  }
}

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