Submission #646084

#	Time	Username	Problem	Language	Result	Execution time	Memory
646084		Tudy006	Sum Zero (RMI20_sumzero)	C++14	61 / 100	415 ms	26300 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

unordered_map <long long, int> f;

const int NMAX = 4e5;
const int LOG4MAX = 9;
//const int LOG2MAX = 18;

int max_left4[NMAX + 1][LOG4MAX + 1];
//int max_left2[NMAX + 1][LOG2MAX + 1];
int v[NMAX + 1];

//ifstream fin( "sumzero.in" );
//ofstream fout( "sumzero.out" );

void calc_max_left4( int n ) {
    long long s = 0;
    f.clear();
    for ( int i = 1; i <= n; i ++ ) {
        s += v[i];
        if ( f[s] == 0 && s != 0 ) max_left4[i][0] = max_left4[i - 1][0];
        else max_left4[i][0] = max( max_left4[i - 1][0], f[s] + 1 );
        f[s] = i;
    }
    for ( int i = 1; i <= n; i ++ ) {
        for ( int j = 1; ( 1 << ( 2 * j ) ) <= i; j ++ ) {
            if ( max_left4[i][j - 1] == 0 ||
                 max_left4[max_left4[i][j - 1] - 1][j - 1] == 0 ||
                 max_left4[max_left4[max_left4[i][j - 1] - 1][j - 1] - 1][j - 1] == 0 )
            max_left4[i][j] = 0;
            else max_left4[i][j] = max_left4[max_left4[max_left4[max_left4[i][j - 1] - 1][j - 1] - 1][j - 1] - 1][j - 1];
            ///cout << max_left4[i][j - 1] << ' ';
        }
    }
}
//void calc_max_left2( int n ) {
//    long long s = 0;
//    f.clear();
//    for ( int i = 1; i <= n; i ++ ) {
//        s += v[i];
//        if ( f[s] == 0 && s != 0 ) max_left2[i][0] = max_left2[i - 1][0];
//        else max_left2[i][0] = max( max_left2[i - 1][0], f[s] + 1 );
//        f[s] = i;
//    }
//    for ( int i = 1; i <= n; i ++ ) {
//        for ( int j = 1; ( 1 << j ) <= i; j ++ ) {
//            if ( max_left2[i][j - 1] == 0 ) max_left2[i][j] = 0;
//            else max_left2[i][j] = max_left2[max_left2[i][j - 1] - 1][j - 1];
//        }
//    }
//}
void read() {
    int n;
    cin >> n;
    for ( int i = 1; i <= n; i ++ ) cin >> v[i];
//    calc_max_left2( n );
    calc_max_left4( n );
}
//int p2_ans( int l, int r ) {
//    int ans = 0, p2 = LOG2MAX;
//    while ( r >= l && p2 >= 0 ) {
//        if ( max_left2[r][p2] >= l ) {
//            ans += ( 1 << p2 );
//            r = max_left2[r][p2] - 1;
//        } else {
//            p2 --;
//        }
//    }
//    return ans;
//}
int p4_ans( int l, int r ) {
    int ans = 0, p4 = LOG4MAX;
    while ( r >= l && p4 >= 0 ) {
        if ( max_left4[r][p4] >= l ) {
            ans += ( 1 << ( 2 * p4 ) );
            r = max_left4[r][p4] - 1;
        } else {
            p4 --;
        }
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
    read();
    int q;
    cin >> q;
    for ( int i = 1; i <= q; i ++ ) {
        int l, r;
        cin >> l >> r;
        cout << p4_ans( l, r ) << '\n';
    }
    return 0;
}

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