제출 #1099224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1099224		vjudge1	Sum Zero (RMI20_sumzero)	C++17	22 / 100	174 ms	21816 KiB

sumzero

#include <bits/stdc++.h>

#define int long long
#define ar array

using namespace std;

const int N = 2e5 + 20;
const int LOG = 20;
const int INF = 1e18;
const int MOD = 1e9 + 7;


signed main() {ios_base::sync_with_stdio(false);cin.tie(NULL);
	int n;
	cin>>n;
	int A[n];
	for(int i = 0;i < n;i++)cin>>A[i];
	map<int,int> mp;
	int nxt[n + 2];
	for(int i= 0;i <= n + 1;i++)nxt[i] = n + 1;
	int sum = 0;
	mp[0] = -1;
	for(int i = 0;i < n;i++){
		sum += A[i];
		if(mp.count(sum)){
			int j = mp[sum] + 1;
			//cout<<i<<" "<<j<<endl;
			nxt[j] = min(nxt[j], i);
		}
		mp[sum] = i;
	}
	for(int i = n - 1;i >= 0;i--)nxt[i] = min(nxt[i], nxt[i + 1]);
	for(int i = 0;i < n;i++){
		if(nxt[i] < n)nxt[i]++;
		//cout<<nxt[i]<<" ";
	}
	//cout<<endl;
	int up[n + 1][LOG];
	for(int i = 0;i <= n + 1;i++)up[i][0] = nxt[i];
	//cout<<endl;
	//assert(0);
	for(int j = 1;j < LOG;j++){
		for(int i = 0;i <= n + 1;i++){
		//cout<<"EWE"<<endl;
			//cout<<up[i][j - 1]<<" ";
			up[i][j] = up[up[i][j - 1]][j - 1];	
		}
		//cout<<endl;
	}
	int q;
	cin>>q;
	while(q--){
		int l, r;
		cin>>l>>r;
		--l;
		int ans = 0;
		for(int i = LOG - 1;i >= 0;i--){
			if(up[l][i] <= r){
				l = up[l][i];
				ans += (1 << i);
			}
		}
		cout<<ans<<endl;
	}
	
}

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