제출 #646068

#제출 시각아이디문제언어결과실행 시간메모리
646068Tudy006Sum Zero (RMI20_sumzero)C++14
0 / 100
10 ms852 KiB
#include <bits/stdc++.h> using namespace std; unordered_map <long long, int> f; const int NMAX = 4e5; int max_left[NMAX + 1][21]; /// max_left[i][j] cel mai mare k pentru care exista 2^j subsecvente de suma 0 intre k si i. int v[NMAX + 1]; void calc_max_left( 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; } for ( int i = 1; i <= n; i ++ ) { for ( int j = 1; ( 1 << j ) <= i; j ++ ) { if ( max_left[i][j - 1] == 0 ) max_left[i][j] = 0; else max_left[i][j] = max_left[max_left[i][j - 1] - 1][j - 1]; } } } int main() { // ifstream fin( "sumzero.in" ); // ofstream fout( "sumzero.out" ); int n, q; cin >> n; for ( int i = 1; i <= n; i ++ ) cin >> v[i]; cin >> q; calc_max_left( n ); for ( int i = 1; i <= n; i ++ ) cout << max_left[i][0] << ' '; for ( int i = 1; i <= q; i ++ ) { int l, r, p2 = 20, ans = 0; cin >> l >> r; while ( r >= l ) { while ( p2 >= 0 && max_left[r][p2] < l ) p2 --; if ( p2 >= 0 ) { ans += ( 1 << p2 ); r = max_left[r][p2] - 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...