제출 #646076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646076		Tudy006	Sum Zero (RMI20_sumzero)	C++14	0 / 100	3 ms	596 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

unordered_map <long long, int> f;

const int NMAX = 4e5;
const int LOG4MAX = 9;

int max_left[NMAX + 1][LOG4MAX + 1]; /// max_left[i][j] cel mai mare k pentru care exista 2^j subsecvente de suma 0 intre k si i.

void calc_max_left() {
    long long s = 0;
    int n, x;
    cin >> n;
    for ( int i = 1; i <= n; i ++ ) {
        cin >> x;
        s += x;
        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;
    }
    for ( int i = 1; i <= n; i ++ ) {
        for ( int j = 1; ( 1 << ( 2 * j ) ) <= i; j ++ ) {
            int x = i + 1;
            for ( int k = 1; k <= 4; k ++ ) {
                x = max_left[x - 1][j - 1];
                if ( x == 0 ) {
                    x = -1;
                    break;
                }
            }
            max_left[i][j] = x + 1;
        }
    }
}
int main() {
    ios_base::sync_with_stdio( false );
    cin.tie( NULL );
    int q;
    calc_max_left();
    cin >> q;
    for ( int i = 1; i <= q; i ++ ) {
        int l, r, p4 = LOG4MAX, ans = 0;
        cin >> l >> r;
        while ( r >= l ) {
            while ( p4 >= 0 && max_left[r][p4] < l ) p4 --;
            if ( p4 >= 0 ) {
                ans += ( 1 << ( 2 * p4 ) );
                r = max_left[r][p4] - 1;
            } else {
                r = 0;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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