Submission #1137941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137941		AbdullahIshfaq	Sum Zero (RMI20_sumzero)	C++20	100 / 100	385 ms	14116 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 998244353
const int lg = 4, N = 4e5 + 1, Base = 32;
int sp[N][lg], power[lg];
void solve(){
	power[0] = 1;
	for(int i = 1; i < lg; i ++){
		power[i] = Base * power[i - 1];
	}
	int n;
	cin >> n;
	vector<int> arr(n);
	for(int i = 0 ;i < n ; i++){
		cin >> arr[i];
	}
	for(int i = 0; i <= n + 1; i++){
    	for(int j = 0; j < lg; j++){
        	sp[i][j] = n + 1;
      	}
    }
	ll sm = 0;
	vector<ll> pre;
    pre.push_back(sm);
    for(int i = n - 1; i >= 0; i--){
      sm += arr[i];
      pre.push_back(sm);
    }
    sort(pre.begin(), pre.end());
    pre.resize(unique(pre.begin(), pre.end()) - pre.begin());
    sm = 0;
    vector<int> last(pre.size(), n + 1);
    last[lower_bound(pre.begin(), pre.end(), sm) - pre.begin()] = n;
    for(int i = n - 1; i >= 0; i--){
		sm += arr[i];
		sp[i][0] = last[lower_bound(pre.begin(), pre.end(), sm) - pre.begin()];
		last[lower_bound(pre.begin(), pre.end(), sm) - pre.begin()] = i;
	}
	for(int i = n - 2; i >= 0; i--){
		sp[i][0] = min(sp[i][0], sp[i + 1][0]);
	}
	for(int j = 1; j < lg; j++){
		for(int i = 0; i < n; i++){
			int x = i;
			for (int k = 0; k < Base; k++) {
				x = sp[x][j - 1];
			}
			sp[i][j] = x;
		}
    }
	int q;
	cin >> q;
	for(int i = 0; i < q; i ++){
		int l, r;
		cin >> l >> r;
		l--;
		int ans = 0;
		int x = lg - 1;
		while(x >= 0){
			if(sp[l][x] <= r){
				ans += power[x];
				l = sp[l][x];
			}
			else{
				x--;
			}
		}
		cout << ans << '\n';
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for (ll i = 1; i <= tests; i++) {
		solve();
	}
}

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