Submission #1273317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273317		reginox	Sum Zero (RMI20_sumzero)	C++20	61 / 100	303 ms	28832 KiB

sumzero

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 4e5+3;
const int K = 9;
int n, a[N];
int b[N];
int sp[N][K+1];

void init(){
  map<int, int> last;
  fill(b, b+N, n+1);
  last[0] = n;
  int su = 0;
  for(int i = n; i >= 1; i--){
    su += a[i];
    if(last.find(su) == last.end()) b[i] = n+1;
    else b[i] = last[su];
    if(i < n) b[i] = min(b[i], b[i+1]);
    last[su] = i-1;
  }
  // for(int i = 1; i <= n; i++) cout << b[i] << " ";
  // cout << "\n";
}

void init2(){
  for(int i = 1; i <= N-1; i++) sp[i][0] = b[i]+1;
  for(int i = 1; i <= K; i++){
    for(int j = 1; j <= n+2; j++) sp[j][i] = n+2;
    for(int j = 1; j + (1 << (i << 1)) - 1 <= n; j++){
      sp[j][i] = sp[j][i-1];
      sp[j][i] = sp[sp[j][i]][i-1];
      sp[j][i] = sp[sp[j][i]][i-1];
      sp[j][i] = sp[sp[j][i]][i-1];
    }
  }
}

int solve(int l, int r){
  int st = 0;
  for(int i = K; i >= 0; i--){
    while(sp[l][i] <= r+1){
      l = sp[l][i];
      st += 1 << (i << 1);
    }
    // cerr << i << " " << l << "\n";
    if(l > r) break;
  }
  return st;
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  init();
  init2();
  int q; cin >> q;
  while(q--){
    int l, r; cin >> l >> r;
    cout << solve(l, r) << "\n";
  }
  return 0;
}

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