oj.uz

Submission #537903

# Submission time Handle Problem Language Result Execution time Memory
537903 2022-03-15T19:59:33 Z vladislav11 Sum Zero (RMI20_sumzero) C++14
100 / 100
 345 ms 20396 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 83 ms 3452 KB Output is correct
8 Correct 77 ms 3588 KB Output is correct
9 Correct 76 ms 3584 KB Output is correct
10 Correct 78 ms 3596 KB Output is correct
11 Correct 72 ms 3592 KB Output is correct
12 Correct 78 ms 3584 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 83 ms 3452 KB Output is correct
8 Correct 77 ms 3588 KB Output is correct
9 Correct 76 ms 3584 KB Output is correct
10 Correct 78 ms 3596 KB Output is correct
11 Correct 72 ms 3592 KB Output is correct
12 Correct 78 ms 3584 KB Output is correct
13 Correct 317 ms 13324 KB Output is correct
14 Correct 308 ms 13664 KB Output is correct
15 Correct 328 ms 13816 KB Output is correct
16 Correct 328 ms 13496 KB Output is correct
17 Correct 305 ms 20364 KB Output is correct
18 Correct 345 ms 20396 KB Output is correct