Submission #1242025

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

sumzero

// #pragma GCC target ("avx2")
// #pragma GCC optimize ("O3")
// #pragma GCC optimize ("unroll-loops")

// #include <bits/stdc++.h>
#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 int long long
#define endl "\n"

void solve() {
	int n; cin >> n;
	map<int , int> c;
	int a[n + 2], p[n + 2] = {};
	int bl[n + 2][18] = {{}};
	int l = 0;
	
	// for (int i = 0; i <= n; i++){
		// for (int j = 0; j < 18; j++) bl[i][j] = -1;
	// }
	
	c[0] = 1;
	
	for (int i = 2; i <= n + 1; i++){
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
		if (p[i] == p[c[p[i]]]){
			l = max(l, c[p[i]]);
		}
		bl[i][0] = l;
		c[p[i]] = i;
		// cout << l << ' ';
		// cout << endl;
	}
	// cout << endl;
	for (int j = 1; j <= 17; j++){
		for (int i = 1; i <= n + 1; i++){
			bl[i][j] = bl[bl[i][j - 1]][j - 1];
		}
	}
	int q; cin >> q;
	for (int i = 1; i <= q; i++){
		int l, r; cin >> l >> r;
		l++, r++;
		int ans = 0;
		int j = 17;
		while (j >= 0){
			// cout << l - 1 << ' ' << bl[r][j] <<  ' ' << j << endl;
			if (bl[r][j] >= l - 1){
				ans += (1ll << j);
				r = bl[r][j];
				// cout << r  << ' ' << j << endl;
			}
			j--;
		}
		cout << ans << endl;
		// cout << endl;
	}
    return;
}

signed main() {
    // freopen("", "r", stdin);
    // freopen("", "w", stdout);	
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << setprecision(9);
    srand(time(0));

    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}

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