제출 #715776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
715776		snpmrnhlol	Sum Zero (RMI20_sumzero)	C++11	61 / 100	374 ms	21936 KiB

sumzero

#include <iostream>
#include <algorithm>
using namespace std;
int v[400001];
struct numbers
{
    int nr;
    int id;
} ps[400001];
int jump[400005][9];
int f[400001];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,i,nr = 2e9,j,l,r,cnt = -1;
    int cur = -1;
    cin>>n;
    for(i = 0; i < n; i++)
    {
        cin>>v[i];
        ps[i + 1] = {ps[i].nr + v[i],i + 1};
    }
    sort(ps,ps + n + 1,[&](numbers a,numbers b)
    {
        return a.nr < b.nr;
    });
    for(i = 0; i <= n; i++)
    {
        if(cur != ps[i].nr)
        {
            cur = ps[i].nr;
            cnt++;
        }
        ps[i].nr = cnt;
    }
    sort(ps,ps + n + 1,[&](numbers a,numbers b)
    {
        return a.id < b.id;
    });
    f[ps[n].nr] = n;
    for(i = n - 1; i >= 0; i--)
    {
        if(f[ps[i].nr] != 0 && nr > f[ps[i].nr])
        {
            nr = f[ps[i].nr];
        }
        jump[i][0] = (nr==2e9?n + 1:nr);
        f[ps[i].nr] = i;
    }
    jump[n + 1][0] = n + 1;
    jump[n][0] = n + 1;
    for(i = 1; i <= 8;i++)
    {
        for(j = 0; j <= n + 1; j++)
        {
            ///quad jump
            jump[j][i] = jump[jump[jump[jump[j][i - 1]][i - 1]][i - 1]][i - 1];
        }
    }
    int q,ans = 0,p;
    cin>>q;
    for(i = 0; i < q; i++)
    {
        cin>>l>>r;
        l--;
        r--;
        cur = l,ans = 0;
        for(j = 8; j >= 0; j--)
        {
            for(p = 0;p < 4;p++){
                if(cur != n && jump[cur][j] <= r + 1)
                {
                    cur = jump[cur][j];
                    ans+=(1<<(j*2));
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

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