Submission #857707

#	Time	Username	Problem	Language	Result	Execution time	Memory
857707		alexdumitru	Sum Zero (RMI20_sumzero)	C++17	61 / 100	225 ms	27812 KiB

sumzero

#include <bits/stdc++.h>
 
using namespace std;
 
const int NMAX = 500005;
const int LMAX = 20;
 
int n, q, a[NMAX], Next[NMAX], jump[NMAX];
long long sp[NMAX];
map<long long, int> mp;
int L[NMAX], R[NMAX], ANS[NMAX];
 
 
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sp[i] = sp[i - 1] + a[i];
    }
    Next[n + 1] = Next[n + 2] = n + 2;
    for(int i = n; i >= 1; i--)
    {
        Next[i] = Next[i + 1];
        mp[sp[i]] = i;
        if(mp[sp[i - 1]])
            Next[i] = min(Next[i], mp[sp[i - 1]] + 1);
    }
    cin >> q;
    for(int i = 1; i <= q; i++)
        cin >> L[i] >> R[i];
 
    for(int lg = LMAX; lg >= 0; lg--)
    {
        for(int i = 1; i <= n + 2; i++)
            jump[i] = Next[i];
        for(int k = 1; k <= lg; k++)
            for(int i = 1; i <= n + 2; i++)
                jump[i] = jump[jump[i]];
        for(int i = 1; i <= q; i++)
            if(jump[L[i]] <= R[i] + 1)
            {
                ANS[i] += (1 << lg);
                L[i] = jump[L[i]];
            }
    }
    for(int i = 1; i <= q; i++)
        cout << ANS[i] << '\n';
}
 
int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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