Submission #1272848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272848		Taxiradio	Sum Zero (RMI20_sumzero)	C++20	0 / 100	8 ms	1340 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;

#define int int64_t

int32_t main() {
	int n; cin >> n;
	vector<int> a ={0};
	vector<int> c ={0};
	for(int i = 0; i < n; i++){
		int b; cin >> b;
		a.push_back(b);
		c.push_back(c.back() + b);
	}
	vector<int> dp(n+2 , n+1);
	map<int , int> e;
	for(int i = n; i > 0; i--){
		e[c[i]] = i;
		dp[i] = dp[i+1];
		if(e[c[i-1]] != 0){
			dp[i] = min(dp[i] , e[c[i-1]]+1);
		}
	}
	vector<int> v(n+2);
	vector<array<int , 20>> bl(n+2);
	for(int i = 0; i < 20; i++)bl.back()[i] = n+1;
	for(int i = n; i > 0; i--){
		bl[i][0] = dp[i];
		for(int j = 1; j < 20; j++){
			bl[i][j] = bl[bl[i][j-1]][j-1];
		}
		v[i] = v[dp[i]]+1;
	}
	int q; cin >> q;
	while(q--){
		int l , r; cin >> l >> r;
		int w = l;
		for(int i = 19; i >= 0; i--){
			if(bl[w][i]-1 <= r)w = bl[w][i];
		}
		cout << v[l]-v[w] << "\n";
	}
}

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