Submission #1242034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242034		muhammad-ahmad	Sum Zero (RMI20_sumzero)	C++20	61 / 100	611 ms	53944 KiB

sumzero

#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <numeric>
#include <stack>
using namespace std;

#define endl "\n"

void solve() {
	int n; cin >> n;
	map<int , int> c;
	vector<int> a(n + 2), p(n + 2);
	vector<vector<int>> bl(n + 2, vector<int>(16)); // kept but no pre-zero

	int l = 0;
	c[0] = 1;

	for (int i = 2; i <= n + 1; i++){
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
		if (c.count(p[i]) && p[i] == p[c[p[i]]]){
			l = max(l, c[p[i]]);
		}
		bl[i][0] = l;
		c[p[i]] = i;
	}

	for (int j = 1; j <= 15; j++){
		for (int i = 1; i <= n + 1; i++){
			bl[i][j] = bl[bl[i][j - 1]][j - 1];
		}
	}

	int q; cin >> q;
	while (q--){
		int l, r; cin >> l >> r;
		l++, r++;
		int ans = 0;
		for (int j = 15; j >= 0; j--){
			if (bl[r][j] >= l - 1){
				ans += (1ll << j);
				r = bl[r][j];
			}
		}
		cout << ans << endl;
	}
	return;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int tc = 1;
	while (tc--) solve();
	return 0;
}

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