제출 #859424

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
859424		Denkata	Sum Zero (RMI20_sumzero)	C++14	61 / 100	545 ms	24772 KiB

sumzero

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 4e5+3;
const int base = 100;
const int maxlog = 3;
int sparse[maxlog][maxn];
int i,j,p,q,n,m,k,a[maxn],Q,st[3],l,r;
unordered_map <long long,int> enc;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    st[0] = 1;
    st[1] = base;
    st[2] = base*base;
    for(i=1; i<=n; i++)
        cin>>a[i];
    p = -1;
    sparse[0][0] = -1;
    long long sum = 0;
    for(i=1; i<=n; i++)
    {
        sum = sum+a[i];
        if(enc[sum]!=0 || sum==0)
            p = max(p,enc[sum]);
        sparse[0][i] = p;
        enc[sum] = i;
       // cout<<sparse[0][i]<<endl;
    }
    for(i=1; i<maxlog; i++)
    {
        sparse[i][0] = -1;
        for(k=1; k<=n; k++)
        {
            sparse[i][k] = sparse[i-1][k];
            for(j=1;sparse[i][k]!=-1 &&  j<base; j++)
                sparse[i][k] = sparse[i-1][sparse[i][k]];
        }
    }
    cin>>Q;
    for(i=1; i<=Q; i++)
    {
        cin>>l>>r;
        int ans = 0;
        for(j=maxlog-1; j>=0; j--)
        {
            //cout<<j<<" "<<r<<" "<<sparse[j][r]<<endl;
            while(sparse[j][r]>=l-1)
            {
                ans+=st[j];
                r = sparse[j][r];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/**
10
1 2 -3 0 1 -4 3 2 -1 1
3
1 10
1 5
2 9

*/

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