Submission #646824

#	Time	Username	Problem	Language	Result	Execution time	Memory
646824		Tudy006	Sum Zero (RMI20_sumzero)	C++14	100 / 100	282 ms	20400 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 4e5;
const int LOGMAX = 18;

int max_left[NMAX + 1][2];
int l[NMAX + 1];
int r[NMAX + 1];
int ans[NMAX + 1];

pair <int, int> sums[NMAX + 1];

void init( int n ) {
    long long s = 0;
    int x;
    for ( int i = 1; i <= n; i ++ ) {
        cin >> x;
        s += x;
        sums[i] = { s, i };
    }
    sums[0] = { 0, 0 };
    sort( sums, sums + n + 1 );
    for ( int i = 1; i <= n; i ++ ) {
        if ( sums[i].first == sums[i - 1].first )
            max_left[sums[i].second][0] = sums[i - 1].second + 1;
    }
    for ( int i = 1; i <= n; i ++ ) {
        max_left[i][0] = max( max_left[i][0], max_left[i - 1][0] );
    }
}
void calc_max_left( int n, int k ) {
    if ( k == 0 ) {
        for ( int i = 1; i <= n; i ++ ) max_left[i][1] = max_left[i][0];
        return;
    }
    for ( int i = 1; i <= n; i ++ ) {
        if ( max_left[i][0] == 0 ) max_left[i][1] = 0;
        else max_left[i][1] = max_left[max_left[i][0] - 1][0];
    }
    for ( int j = 2; j <= k; j ++ ) {
        for ( int i = n; i >= 1; i -- ) {
            if ( max_left[i][1] == 0 ) max_left[i][1] = 0;
            else max_left[i][1] = max_left[max_left[i][1] - 1][1];
        }
    }
}
int main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
//    ifstream cin( "sumzero.in" );
//    ofstream cout( "sumzero.out" );
    int n, q;
    cin >> n;
    init( n );
    cin >> q;
    for ( int i = 1; i <= q; i ++ ) {
        cin >> l[i] >> r[i];
    }
    for ( int bit = LOGMAX; bit >= 0; bit -- ) {
        calc_max_left( n, bit );
//        cout << "For the bit " << bit << ": ";
//        for ( int i = 1; i <= n; i ++ ) cout << max_left[i][1] << ' ';
//        cout << endl;
        for ( int i = 1; i <= q; i ++ ) {
            if ( max_left[r[i]][1] >= l[i] ) {
                r[i] = max_left[r[i]][1] - 1;
                ans[i] += ( 1 << bit );
            }
        }
    }
    for ( int i = 1; i <= q; i ++ ) cout << ans[i] << '\n';
    return 0;
}

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