Submission #716205

#	Time	Username	Problem	Language	Result	Execution time	Memory
716205		snpmrnhlol	Sum Zero (RMI20_sumzero)	C++17	61 / 100	440 ms	24820 KiB

sumzero

    #include <iostream>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    int v[400001];
    struct numbers
    {
        ll nr;
        int id;
    } ps[400001];
    int jump[400005][5];
    int f[400001];
    int main()
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n,i,nr = 2e9,j,l,r,cnt = -1;
        ll 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 <= 4;i++)
        {
            for(j = 0; j <= n + 1; j++)
            {
                ///octo jump
                jump[j][i] = jump[jump[jump[jump[jump[jump[jump[jump[j][i - 1]][i - 1]][i - 1]][i - 1]][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 = 4; j >= 0; j--)
            {
                for(p = 0;p < (j==4?16:8);p++){
                    if(cur != n && jump[cur][j] <= r + 1)
                    {
                        cur = jump[cur][j];
                        ans+=(1<<(j*3));
                    }
                }
            }
            cout<<ans<<'\n';
        }
        return 0;
    }

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