Submission #942981

#	Time	Username	Problem	Language	Result	Execution time	Memory
942981		vjudge1	Sum Zero (RMI20_sumzero)	C++17	22 / 100	1058 ms	2436 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();

  struct Node {
    int d, j, p;
  };
  
  std::vector<Node> t(n + 2);
  t[n + 1] = {0, n + 1, -1};
  
  for (int i = n, p = n + 1; i >= 0; i--) {
    p = std::min(p, R[i]);
    t[i].p = p;
    t[i].d = t[p].d;
    int p2 = t[p].j;
    if (t[p].d - t[p2].d == t[p2].d - t[t[p2].j].d) {
      t[i].j = t[p2].j;
    } else {
      t[i].j = p;
    }
  }

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

    int counter = 0;
    int u = l;
    while (t[u].p <= r) {
      if (t[u].j <= r) {
        counter += t[u].d - t[t[u].j].d;
        u = t[u].j;
      } else {
        counter++;
        u = t[u].p;
      }
    }
    
    std::cout << counter << nl;
  }
}

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