Submission #1263409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263409		mine255	Sum Zero (RMI20_sumzero)	C++20	61 / 100	272 ms	51608 KiB

sumzero

#include <bits/stdc++.h>
#define _FILE "TEMP"
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define MASK(i) (1ll << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

int n;
ll pre[400007];
vector<ll> b;
int f[400007];
int up[400007][27];

int main() {

  ios_base::sync_with_stdio(0);
  cin.tie(nullptr); cout.tie(nullptr);

  #ifdef EMERGENCY_DEBUG
  freopen(_FILE".inp","r",stdin);
  freopen(_FILE".out","w",stdout);
  #endif

  cin >> n;
  for (int i=1; i<=n; i++) {
    cin >> pre[i];
    pre[i] += pre[i-1];
    b.push_back(pre[i]);
  }

  sort(b.begin(),b.end());
  b.resize(unique(b.begin(),b.end())-b.begin());

  up[n+1][0] = INT_MAX;
  for (int i=n; i>0; i--) {
    up[i][0] = INT_MAX;
    
    int it1 = lower_bound(b.begin(),b.end(),pre[i]) - b.begin() + 1;
    int it2 = lower_bound(b.begin(),b.end(),pre[i-1]) - b.begin() + 1;

    f[it1] = i;

    if (f[it2] != 0) up[i][0] = f[it2]+1;

    up[i][0] = min(up[i][0],up[i+1][0]);
  }

  for (int j=1; j<=20; j++) {
    for (int i=1; i<=n+1; i++) {
      if (up[i][j-1] == INT_MAX || up[up[i][j-1]][j-1] == INT_MAX) up[i][j] = INT_MAX;
      else up[i][j] = up[up[i][j-1]][j-1];
    }
  }

  int q;
  cin >> q;

  while (q--) {
    int l,r;
    cin >> l >> r;

    ll res = 0;
    for (int i=__lg(r-l+1)+1; i>=0; i--) {
      if (up[l][i] > r+1) continue;
      // cerr << l << ' ' << i << '\n';
      res += MASK(i);
      l = up[l][i];
    }

    cout << res << '\n';
  }

  return 0;
}

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