Submission #942471

#	Time	Username	Problem	Language	Result	Execution time	Memory
942471		vjudge1	Sum Zero (RMI20_sumzero)	C++17	100 / 100	193 ms	18000 KiB

sumzero

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

#define ll long long
#define pli pair <ll, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 4e5, LOG = 18, MOD = 5e4+3;

int RD = chrono::steady_clock::now().time_since_epoch().count();

struct hash_table{
	vector <pli> arr[MOD];
	int hash_val(ll x){
		return ((x^RD)%MOD+MOD)%MOD;
	}
	void add(ll x, int y){
		int tmp = hash_val(x);
		for (int i = 0; i < isz(arr[tmp]); i++){
			if (arr[tmp][i].fi == x){
				arr[tmp][i].se = y;
				return;
			}
		}
		arr[tmp].push_back(mp(x, y));
	}
	int get(ll x){
		int tmp = hash_val(x);
		for (int i = 0; i < isz(arr[tmp]); i++){
			if (arr[tmp][i].fi == x) return arr[tmp][i].se;
		}
		return -1;
	}
} lst;

struct node{
	int dep, jump;
};

int n, q, a[NM+5], nxt[NM+5];
ll pref[NM+5];
node T[NM+5];

void add_node(int u){
	int p = nxt[u];
	T[u].dep = T[p].dep+1;
	if (T[p].dep-T[T[p].jump].dep == T[T[p].jump].dep-T[T[T[p].jump].jump].dep){
		T[u].jump = T[T[p].jump].jump;
	}
	else{
		T[u].jump = p;
	}
}

int get(int l, int r){
	int res = 0;
	while (nxt[l] <= r){
		if (T[l].jump <= r){
			res += T[l].dep-T[T[l].jump].dep;
			l = T[l].jump;
		}
		else{
			res++;
			l = nxt[l];
		}
	}
	return res;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		pref[i] = pref[i-1]+a[i];
	}
	nxt[n+1] = n+1;
	for (int i = n; i >= 0; i--){
		nxt[i] = nxt[i+1];
		int tmp = lst.get(pref[i]);
		if (tmp != -1) nxt[i] = min(nxt[i], tmp);
		lst.add(pref[i], i);
	}
	T[n+1].jump = n+1;
	T[n+1].dep = 0;
	for (int i = n; i >= 0; i--){
		add_node(i);
	}
	cin >> q;
	while (q--){
		int l, r; cin >> l >> r;
		cout << get(l-1, r) << '\n';
	}
	return 0;
}

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