Submission #856466

#	Time	Username	Problem	Language	Result	Execution time	Memory
856466		alexia_726	Sum Zero (RMI20_sumzero)	C++17	22 / 100	1032 ms	5184 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;

long long sum[NMAX + 5];

int nxt[NMAX + 5];

int n, q;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>sum[i];
        sum[i]+=sum[i-1];
    }

    map<int, int>pos;

    nxt[n+1]=n+1;

    for(int i=n;i>0;i--)
        {
        pos[sum[i]]=i;
        if (!pos.count(sum[i-1]))
        
            nxt[i]=n+1;
        
       else
            nxt[i]=pos[sum[i-1]];
        
        nxt[i]=min(nxt[i], nxt[i+1]);
    }

    cin>>q;

  for(int i=1;i<=q;++i)
    {
        int l, r;

        cin>>l>>r;

        int answer=0;

        while(nxt[l]<=r)
        {
            l=nxt[l]+1;
            answer++;
        }

        cout<<answer<<'\n';
    }

    return 0;
}

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