제출 #646088

#제출 시각아이디문제언어결과실행 시간메모리
646088Tudy006Sum Zero (RMI20_sumzero)C++14
61 / 100
429 ms24408 KiB
#include <bits/stdc++.h> using namespace std; unordered_map <long long, int> f; const int NMAX = 4e5; const int LOG4MAX = 9; //const int LOG2MAX = 18; int max_left4[NMAX + 1][LOG4MAX + 1]; //int max_left2[NMAX + 1][LOG2MAX + 1]; //int v[NMAX + 1]; //ifstream fin( "sumzero.in" ); //ofstream fout( "sumzero.out" ); void calc_max_left4() { 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_left4[i][0] = max_left4[i - 1][0]; else max_left4[i][0] = max( max_left4[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_left4[i][j - 1] == 0 || max_left4[max_left4[i][j - 1] - 1][j - 1] == 0 || max_left4[max_left4[max_left4[i][j - 1] - 1][j - 1] - 1][j - 1] == 0 ) max_left4[i][j] = 0; else max_left4[i][j] = max_left4[max_left4[max_left4[max_left4[i][j - 1] - 1][j - 1] - 1][j - 1] - 1][j - 1]; ///cout << max_left4[i][j - 1] << ' '; } } } //void calc_max_left2( int n ) { // long long s = 0; // f.clear(); // for ( int i = 1; i <= n; i ++ ) { // s += v[i]; // if ( f[s] == 0 && s != 0 ) max_left2[i][0] = max_left2[i - 1][0]; // else max_left2[i][0] = max( max_left2[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_left2[i][j - 1] == 0 ) max_left2[i][j] = 0; // else max_left2[i][j] = max_left2[max_left2[i][j - 1] - 1][j - 1]; // } // } //} void read() { // int n; // cin >> n; // for ( int i = 1; i <= n; i ++ ) cin >> v[i]; // calc_max_left2( n ); calc_max_left4(); } //int p2_ans( int l, int r ) { // int ans = 0, p2 = LOG2MAX; // while ( r >= l && p2 >= 0 ) { // if ( max_left2[r][p2] >= l ) { // ans += ( 1 << p2 ); // r = max_left2[r][p2] - 1; // } else { // p2 --; // } // } // return ans; //} int p4_ans( int l, int r ) { int ans = 0, p4 = LOG4MAX; while ( r >= l && p4 >= 0 ) { if ( max_left4[r][p4] >= l ) { ans += ( 1 << ( 2 * p4 ) ); r = max_left4[r][p4] - 1; } else { p4 --; } } return ans; } int main() { ios_base::sync_with_stdio( false ); cin.tie( NULL ); read(); int q; cin >> q; for ( int i = 1; i <= q; i ++ ) { int l, r; cin >> l >> r; cout << p4_ans( l, r ) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...