Submission #942951

#	Time	Username	Problem	Language	Result	Execution time	Memory
942951		vjudge1	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1036 ms	12608 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<std::pair<int64_t, int>> vals(n + 1);
  vals[0] = {0, 0};
  int64_t sum = 0;
  for (int i = 1; i <= n; i++) {
    int x;
    std::cin >> x;
    sum += x;
    vals[i] = {sum, i};
  }

  std::sort(vals.begin(), vals.end());
  std::vector<int> R(n + 1);
  
  for (int i = 0; i <= n; i++) {
    int j = i;
    while (j <= n && vals[i].first == vals[j].first) {
      j++;
    }
    
    // now we talking
    R[vals[j - 1].second] = n + 1;
    for (int k = j - 2; k >= i; k--) {
      R[vals[k].second] = vals[k + 1].second;
    }
  }

  vals.clear();
  vals.shrink_to_fit();
  
  std::vector<int> jump(n + 2), depth(n + 2), parent(n + 2);
  jump[n + 1] = n + 1;
  
  for (int i = n, to = n + 1; i >= 0; i--) {
    to = std::min(to, R[i]);
    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];
    }
  }

  int Q;
  std::cin >> Q;
  while (Q--) {
    int l, r;
    std::cin >> l >> r;
    l--;

    int counter = 0;
    int u = l;
    int iter = 0;
    while (u < r) {
      iter++;
      assert(iter < 80);
      if (parent[u] > r) break;
      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