Submission #646815

#TimeUsernameProblemLanguageResultExecution timeMemory
646815Tudy006Sum Zero (RMI20_sumzero)C++14
61 / 100
332 ms22328 KiB
#include <bits/stdc++.h> using namespace std; map <long long, int> f; 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]; void init( int n ) { long long s = 0; int x; 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; } } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...