Submission #1214736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214736		vukhacminh	Sum Zero (RMI20_sumzero)	C++20	61 / 100	529 ms	80588 KiB

sumzero

/**
*    Author :  Vu Khac Minh
**/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 4e5 + 5;
const int mod = 1e9+7;
ll n,nquery,a[maxn],nxt[maxn][22];
pair<ll,ll> b[maxn];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i =1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
        b[i] = {a[i],i};
    }
    b[0] = {0,0};
    sort(b,b+n+1);
    for(int i =0;i<n;i++)
    {
        if(b[i].first == b[i+1].first) a[b[i].second] = b[i+1].second;
        else a[b[i].second] = n+1;
    }
    a[b[n].second] = n+1;
    for(int i =0;i<=n;i++) nxt[i][0] = a[i];
    for(int i = 0;i<20;i++) nxt[n+1][i] = n+1;
    for(int i =n;i>=0;i--)
    {
        nxt[i][0] = min(nxt[i][0],nxt[i+1][0]);
        for(int j = 1;j<20;j++)
            nxt[i][j] = nxt[nxt[i][j-1]][j-1];
    }
    cin>>nquery;
    while(nquery--)
    {
        int l,r,res=0;
        cin>>l>>r;
        l--;
        for(int  i = 19;i>=0;i--)
        {
            while(nxt[l][i]<=r)
            {
                l = nxt[l][i];
                res += (1ll<<i);
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}

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