oj.uz

Submission #942471

# Submission time Handle Problem Language Result Execution time Memory
942471 2024-03-10T17:19:04 Z vjudge1 Sum Zero (RMI20_sumzero) C++17
100 / 100
 193 ms 18000 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 43 ms 11312 KB Output is correct
8 Correct 36 ms 11352 KB Output is correct
9 Correct 42 ms 10328 KB Output is correct
10 Correct 40 ms 11236 KB Output is correct
11 Correct 37 ms 11088 KB Output is correct
12 Correct 40 ms 10328 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6748 KB Output is correct
7 Correct 43 ms 11312 KB Output is correct
8 Correct 36 ms 11352 KB Output is correct
9 Correct 42 ms 10328 KB Output is correct
10 Correct 40 ms 11236 KB Output is correct
11 Correct 37 ms 11088 KB Output is correct
12 Correct 40 ms 10328 KB Output is correct
13 Correct 181 ms 16976 KB Output is correct
14 Correct 175 ms 17632 KB Output is correct
15 Correct 188 ms 13396 KB Output is correct
16 Correct 193 ms 18000 KB Output is correct
17 Correct 176 ms 16520 KB Output is correct
18 Correct 186 ms 13652 KB Output is correct