Submission #1225658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225658		MuhammadSaram	Sum Zero (RMI20_sumzero)	C++20	61 / 100	127 ms	39480 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 1e5+5, lg = 17;

int nxt[M][lg],a[M],pre[M];
map<int,vector<int>> ind;

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
		cin>>a[i],pre[i]=pre[i-1]+a[i];
	for (int i=n;i>=0;i--)
		ind[pre[i]].push_back(i);
	set<int> se={n+1};
	for (auto [x,v]:ind)
		if (v.size()>1)
			se.insert(v[v.size()-2]);
	for (int i=1;i<=n+1;i++)
	{
		nxt[i][0]=*se.begin();
		ind[pre[i-1]].pop_back();
		int m=ind[pre[i-1]].size();
		if (m)
			se.erase(ind[pre[i-1]].back());
		if (m>1)
			se.insert(ind[pre[i-1]][m-2]);
	}
	nxt[n+2][0]=n+1;
	for (int p=1;p<lg;p++)
		for (int i=1;i<=n+2;i++)
			nxt[i][p]=nxt[nxt[i][p-1]+1][p-1];
	int q;
	cin>>q;
	while (q--)
	{
		int l,r;
		cin>>l>>r;
		int ans=0;
		for (int p=lg-1;p>=0;p--)
			if (nxt[l][p]<=r)
				ans+=(1<<p),l=nxt[l][p]+1;
		cout<<ans<<'\n';
	}
	
	return 0;
}

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