oj.uz

Submission #646824

# Submission time Handle Problem Language Result Execution time Memory
646824 2022-09-30T19:00:07 Z Tudy006 Sum Zero (RMI20_sumzero) C++14
100 / 100
 282 ms 20400 KB 
#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.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 58 ms 3504 KB Output is correct
8 Correct 58 ms 3448 KB Output is correct
9 Correct 63 ms 3476 KB Output is correct
10 Correct 73 ms 3516 KB Output is correct
11 Correct 54 ms 3512 KB Output is correct
12 Correct 59 ms 3508 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 58 ms 3504 KB Output is correct
8 Correct 58 ms 3448 KB Output is correct
9 Correct 63 ms 3476 KB Output is correct
10 Correct 73 ms 3516 KB Output is correct
11 Correct 54 ms 3512 KB Output is correct
12 Correct 59 ms 3508 KB Output is correct
13 Correct 239 ms 13264 KB Output is correct
14 Correct 233 ms 13012 KB Output is correct
15 Correct 256 ms 13428 KB Output is correct
16 Correct 245 ms 19420 KB Output is correct
17 Correct 236 ms 20268 KB Output is correct
18 Correct 282 ms 20400 KB Output is correct