oj.uz

답안 #960457

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
960457 2024-04-10T13:33:08 Z LucaIlie Sum Zero (RMI20_sumzero) C++17
100 / 100
 396 ms 20452 KB 
#include <bits/stdc++.h>


#pragma GCC target("avx2,popcnt")
#pragma GCC optimize("O3,unroll-loops")


const int MAX_N = 4e5;
const int MAX_Q = 4e5;

using namespace std;

int last0[MAX_N + 2], last[MAX_N + 2], l[MAX_Q], r[MAX_Q], ans[MAX_Q], p[MAX_N + 2];
int sp[MAX_N + 1];

int main() {
    int n, q;

    cin >> n;
    sp[0] = 0;
    for ( int i = 1; i <= n; i++ ) {
        int a;
        cin >> a;
        sp[i] = sp[i - 1] + a;
    }
    cin >> q;
    for ( int i = 0; i < q; i++ ) {
        cin >> l[i] >> r[i];
        ans[i] = 0;
    }

    for ( int i = 0; i <= n; i++ )
        p[i] = i;
    sort( p, p + 1 + n, []( int i, int j ) {
        if ( sp[i] == sp[j] )
            return i < j;
        return sp[i] < sp[j];
    } );

    for ( int i = 1; i <= n; i++ ) {
        if ( sp[p[i]] == sp[p[i - 1]] )
            last0[p[i - 1] + 1] = p[i];
    }

    for ( int i = 1; i <= n + 1; i++ ) {
        if ( last0[i] == 0 )
            last0[i] = n + 1;
    }

    for ( int i = n; i >= 1; i-- )
        last0[i] = last0[i] < last0[i + 1] ? last0[i] : last0[i + 1];\

    for ( int niv = log2( n ); niv >= 0; niv-- ) {
        for ( int i = 1; i <= n; i++ )
            last[i] = last0[i];
        for ( int b = 1; b <= niv; b++ ) {
            for ( int i = 1; i <= n; i++ )
                last[i] = last[i] + 1 > n ? n + 1 : last[last[i] + 1];
            last[n + 1] = n + 1;
        }
        for ( int i = 0; i < q; i++ ) {
            if ( last[l[i]] <= r[i] ) {
                ans[i] += (1 << niv);
                l[i] = last[l[i]] + 1;
            }
        }
    }

    for ( int i = 0; i < q; i++ )
        cout << ans[i] << "\n";

    return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 10584 KB Output is correct
2 Correct 8 ms 10704 KB Output is correct
3 Correct 5 ms 10840 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 5 ms 10588 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 10584 KB Output is correct
2 Correct 8 ms 10704 KB Output is correct
3 Correct 5 ms 10840 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 5 ms 10588 KB Output is correct
7 Correct 87 ms 11600 KB Output is correct
8 Correct 103 ms 11112 KB Output is correct
9 Correct 88 ms 11112 KB Output is correct
10 Correct 80 ms 11108 KB Output is correct
11 Correct 92 ms 11100 KB Output is correct
12 Correct 87 ms 11112 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 10584 KB Output is correct
2 Correct 8 ms 10704 KB Output is correct
3 Correct 5 ms 10840 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 5 ms 10588 KB Output is correct
7 Correct 87 ms 11600 KB Output is correct
8 Correct 103 ms 11112 KB Output is correct
9 Correct 88 ms 11112 KB Output is correct
10 Correct 80 ms 11108 KB Output is correct
11 Correct 92 ms 11100 KB Output is correct
12 Correct 87 ms 11112 KB Output is correct
13 Correct 362 ms 13160 KB Output is correct
14 Correct 396 ms 12892 KB Output is correct
15 Correct 384 ms 13660 KB Output is correct
16 Correct 361 ms 13156 KB Output is correct
17 Correct 383 ms 20452 KB Output is correct
18 Correct 386 ms 20440 KB Output is correct