Submission #537903

#	Time	Username	Problem	Language	Result	Execution time	Memory
537903		vladislav11	Sum Zero (RMI20_sumzero)	C++14	100 / 100	345 ms	20396 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = int(4e5)+100;

int n;
ll a[N];
int nxt[N];
int jmp[N];
array<int,3> qer[N];

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

    cin >> n;

    a[0] = 0;
    for ( int i=1; i<=n; i++ )
        cin >> a[i];

    for ( int i=1; i<=n; i++ )
        a[i] += a[i-1];

    for ( int i=0; i<=n+1; i++ )
        nxt[i] = n+1;

    multiset<int> mst;

    mst.insert( 0 );

    for ( int l=0, r=0; l<=n; l++ )
    {
        /*cout << l << ": ";
        for ( auto& el : mst )
            cout << el << ' ';
        cout << '\n';*/

        while ( r <= n )
        {
            if ( mst.count( a[r] ) >= 2 )
                break;

            r++;

            if ( r <= n )
                mst.insert( a[r] );
        }

        /*cout << l << ' ' << r << ": ";
        for ( auto& el : mst )
            cout << el << ' ';
        cout << '\n';*/

        nxt[l+1] = r;
        mst.erase( mst.find( a[l] ) );
    }

    //cout << "here\n";

    /*map<ll,int> pre;

    for ( int i=0; i<=n; i++ )
    {
        if ( pre.count( a[i] ) )
            nxt[ pre[a[i]]+1 ] = i;

        pre[ a[i] ] = i;
    }*/

    /*for ( int i=0; i<=n; i++ )
        cout << nxt[i] << ' ';
    cout << '\n';*/

    for ( int i=n; i>=0; i-- )
        nxt[i] = min( nxt[i], nxt[i+1] );

    int q;
    cin >> q;

    for ( int i=0; i<q; i++ )
    {
        cin >> qer[i][0] >> qer[i][1];
        qer[i][2] = 0;
    }

    for ( int p=20; p>=0; p-- )
    {
        for ( int i=0; i<=n+1; i++ )
            jmp[i] = nxt[i];

        for ( int i=0; i<p; i++ )
        {
            for ( int j=0; j<=n+1; j++ )
                jmp[j] = jmp[ min( n+1, jmp[j]+1 ) ];
        }

        /*cout << p << ": ";
        for ( int i=0; i<=n+1; i++ )
            cout << jmp[i] << ' ';
        cout << '\n';*/

        for ( int i=0; i<q; i++ )
        {
            if ( qer[i][0] <= qer[i][1] && jmp[ qer[i][0] ] <= qer[i][1] )
            {
                qer[i][2] += 1 << p;
                qer[i][0] = jmp[ qer[i][0] ] + 1;
            }
        }
    }

    for ( int i=0; i<q; i++ )
        cout << qer[i][2] << '\n';

    return 0;
}

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