제출 #646080

#제출 시각아이디문제언어결과실행 시간메모리
646080Tudy006Sum Zero (RMI20_sumzero)C++14
0 / 100
3 ms596 KiB
#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 ++ ) { if ( max_left[i][j - 1] == 0 || max_left[max_left[i][j - 1] - 1][j - 1] == 0 || max_left[max_left[max_left[i][j - 1] - 1][j - 1] - 1][j - 1] == 0 ) max_left[i][j] = 0; else max_left[i][j] = max_left[max_left[max_left[max_left[i][j - 1]][j - 1] - 1][j - 1] - 1][j - 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...