Submission #646814

#	Time	Username	Problem	Language	Result	Execution time	Memory
646814		Tudy006	Sum Zero (RMI20_sumzero)	C++14	61 / 100	227 ms	27856 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

unordered_map <long long, int> f;

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

int max_left[NMAX + 1][2];
int v[NMAX + 1];
pair <int, int> querys[NMAX + 1];
int ans[NMAX + 1];

void init( int n ) {
    long long s = 0;
    for ( int i = 1; i <= n; i ++ ) {
        s += v[i];
        if ( f[s] == 0 && s != 0 ) max_left[i][0] = max_left[i - 1][0];
        else max_left[i][0] = max( max_left[i - 1][0], f[s] + 1 );
        f[s] = i;
    }
}
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;
    for ( int i = 1; i <= n; i ++ ) cin >> v[i];
    cin >> q;
    init( n );
    for ( int i = 1; i <= q; i ++ ) {
        cin >> querys[i].first >> querys[i].second;
    }
    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[querys[i].second][1] >= querys[i].first ) {
                querys[i].second = max_left[querys[i].second][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: 0 / 39