Submission #537881

#	Time	Username	Problem	Language	Result	Execution time	Memory
537881		vladislav11	Sum Zero (RMI20_sumzero)	C++14	61 / 100	330 ms	23404 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n;
vector<ll> a;
vector<int> nxt;

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

    cin >> n;

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

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

    map<ll,int> pre;

    nxt.assign( n+2, n+1 );

    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=n; i>=0; i-- )
        nxt[i] = min( nxt[i], nxt[i+1] );

    /*for ( auto& el : nxt )
        cout << el << ' ';
    cout << '\n';*/

    int q;
    cin >> q;

    vector<array<int,3>> qer(q);

    for ( auto& ar : qer )
    {
        cin >> ar[0] >> ar[1];
        ar[2] = 0;
    }

    for ( int p=20; p>=0; p-- )
    {
        vector<int> jmp( nxt.begin(), nxt.end() );

        /*cout << p << ":\n";

        for ( auto& el : jmp )
            cout << el << ' ';
        cout << '\n';*/

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

        /*for ( auto& el : jmp )
            cout << el << ' ';
        cout << '\n';*/

        for ( auto& ar : qer )
        {
            if ( jmp[ ar[0] ] <= ar[1] )
            {
                ar[2] += 1 << p;
                ar[0] = jmp[ ar[0] ] + 1;
            }
        }
    }

    for ( auto& ar : qer )
        cout << ar[2] << '\n';

    return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:67:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for ( int j=0; j<jmp.size(); j++ )
      |                            ~^~~~~~~~~~~

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