제출 #1137131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137131		Pwo	Sum Zero (RMI20_sumzero)	C++20	22 / 100	1093 ms	4008 KiB

sumzero

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

int n, q, a[400005], p[400005];
unordered_map<int, int> mp;

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	int sum = 0; p[0] = -1; mp[0] = 0;
	for (int i = 1; i <= n; i++) {
		sum += a[i];
		p[i] = p[i - 1];
		if (mp.find(sum) != mp.end())
			p[i] = max(p[i], mp[sum]);
		mp[sum] = i;
	}
	
	cin >> q;
	while (q--) {
		int l, r; cin >> l >> r;
		int ans = 0;
		while (r >= l) {
			r = p[r];
			if (r + 1 >= l) ans++;
		}
		cout << ans << '\n';
	}
}

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