| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1136001 | Thanhs | Sum Zero (RMI20_sumzero) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define name "TENBAI"
#define fi first
#define se second
#define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 4e5 + 5;
vector<int> nen;
vector<pair<int32_t, int32_t>> v;
int A[NM];
int32_t n, a[NM][19], pr[NM];
void solve()
{
memset(pr, -1, sizeof pr);
cin >> n;
nen.push_back(0);
for (int i = 1; i <= n; i++)
{
cin >> A[i];
A[i] += A[i - 1];
nen.push_back(A[i]);
}
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()));
for (int i = 0; i <= n; i++)
{
A[i] = lower_bound(nen.begin(), nen.end(), A[i]) - nen.begin();
if (~pr[A[i]])
v.emplace_back(pr[A[i]] + 1, i);
pr[A[i]] = i;
}
sort(v.begin(), v.end(), [&](const auto& x, const auto& y) {return x.fi > y.fi;});
int pt = 0, mn = n + 1;
for (int i = n; i >= 1; i--)
{
while (pt < v.size() && v[pt].fi >= i)
setmin(mn, v[pt++].se);
a[i][0] = mn;
}
a[n + 1][0] = n + 1;
for (int i = 1; (1 << i) <= n; i++)
for (int j = 1; j <= n + 1; j++)
{
if (a[j][i - 1] == n + 1)
a[j][i] = n + 1;
else
a[j][i] = (a[a[j][i - 1] + 1][i - 1]);
}
int q;
cin >> q;
while (q--)
{
int l, r;
cin >> l >> r;
int ans = 0;
for (int i = __lg(n); i >= 0; i--)
if (a[l][i] <= r)
{
ans += 1 << i;
l = a[l][i] + 1;
}
cout << ans << endl;
}
}
signed main()
{
if (fopen("in.txt", "r"))
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}
else if (fopen(name".inp", "r"))
{
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int tc = 1;
// cin >> tc;
while (tc--)
solve();
}