Submission #1177156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177156		altern23	Sum Zero (RMI20_sumzero)	C++17	100 / 100	435 ms	16628 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
 
#define ll int
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 4e5;
const ll INF = 4e18;
const int MOD = 1e9 + 7;

ll up[MAXN + 5][7];
pii a[MAXN + 5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;	
	for(;tc--;){
		ll N; cin >> N;
		ll now = 0;
		for(int i = 1; i <= N; i++){
			ll x; cin >> x;
			now += x;
			a[i] = {now, i};
		}
		
		sort(a, a + 1 + N);
		
		for(int i = 1; i <= N; i++){
			if(a[i].fi == a[i - 1].fi){
				up[a[i - 1].sec][0] = a[i].sec;
			}
		}

		for(int LOG = 0; LOG < 7; LOG++){
			up[N + 1][LOG] = N + 1;
		}
		for(int i = N; i >= 0; --i){
			if(up[i][0] == 0) up[i][0] = N + 1;
			up[i][0] = min(up[i][0], up[i + 1][0]);
		}
		for(int LOG = 1; LOG < 7; LOG++){
			for(int i = 0; i <= N; i++){
				up[i][LOG] = up[up[up[up[i][LOG - 1]][LOG - 1]][LOG - 1]][LOG - 1];
			}
		}
		
		ll Q; cin >> Q;
		for(int i = 1; i <= Q; i++){
			ll l, r; cin >> l >> r;
			--l;
			ll ans = 0;
			for(int LOG = 6; LOG >= 0; --LOG){
				while(up[l][LOG] <= r){
					ans += (1LL << (LOG * 2));
					l = up[l][LOG];
				}
			}
			cout << ans << "\n";
		}
	}   
	
}

/*

*/

Compilation message (stderr)

sumzero.cpp:11:16: warning: overflow in conversion from 'double' to 'int' changes value from '4.0e+18' to '2147483647' [-Woverflow]
   11 | const ll INF = 4e18;
      |                ^~~~

• Subtask 1: 22 / 22
• Subtask 2: 39 / 39
• Subtask 3: 39 / 39