제출 #943955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943955		dubabuba	Sum Zero (RMI20_sumzero)	C++14	61 / 100	1035 ms	34496 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
 
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
 
const int LOG = 9;
const int mxn = 4e5 + 10;
const int inf = 1e9 + 10;
 
int i, j, n, m;
long long pref;
vector<pii> range;
map<long long, int> mp;
int stab[mxn][LOG];
 
int main() {
	cin.tie(0)-> sync_with_stdio(0);
	cin >> n;
	mp[0] = 0;
	for(i = 1; i <= n; i++) {
		cin >> j;
		pref += j;
		auto it = mp.find(pref);
		if(it != mp.end())
			range.push_back(MP((*it).ss + 1, i));
		mp[pref] = i;
	}
 
	mp.clear();
 
	for(i = 0; i < mxn; i++)
	for(j = 0; j < LOG; j++)
		stab[i][j] = inf;
 
	j = 0;
	for(i = 1; i <= n; i++) {
		while(j < (int)range.size() && range[j].ff < i)
			j++;
		if(i <= range[j].ff)
			stab[i][0] = range[j].ss;
	}
 
	for(j = 1; j < LOG; j++)
	for(i = 1; i <= n; i++)
		if(stab[i][j - 1] + 1 <= n)
			stab[i][j] = stab[stab[i][j - 1] + 1][j - 1];
	
	cin >> m;
	int l, r, ans;
	while(m--) {
		cin >> l >> r;
		ans = 0;
 
		for(j = LOG - 1; j >= 0; j--) {
			while(stab[l][j] <= r) {
				l = stab[l][j] + 1;
				ans += (1 << j);
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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