Submission #1225736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225736		Muhammad_Aneeq	Sum Zero (RMI20_sumzero)	C++20	22 / 100	135 ms	22612 KiB

sumzero

#include <iostream>
#include <map>
#include <vector>
#include <deque>
#include <set>
#include <algorithm>
using namespace std;
int const N=1e5+10,LG=19;
int nx[N],mn[N],pre[N];
pair<int,int> calc[N][LG]={};
inline void solve()
{
	int n,q;
	cin>>n;
	map<long long,int>ind;
	ind[0]=-1;
	int a[n];
	for (auto& i:a)
		cin>>i;
	long long sm=0;
	for (int i=0;i<n;i++)
	{
		nx[i]=-1;
		sm+=a[i];
		if (ind.find(sm)!=ind.end())
		{
			pre[i]=ind[sm]+1;
			nx[ind[sm]+1]=i;
		}
		ind[sm]=i;
	}
	for (int i=0;i<=n+1;i++)
		for (int j=0;j<LG;j++)
			calc[i][j]={n,n};
	mn[n]=n+10;
	set<pair<int,int>>s;
	for (int i=n-1;i>=0;i--)
	{
		mn[i]=mn[i+1];
		if (nx[i]!=-1)
		{
			int f=mn[nx[i]+1];
			mn[i]=min(mn[i],nx[i]);
			s.insert({nx[i],i});
		}
		if (s.size()==0)
			continue;
		calc[i][0]=*begin(s);
	}
	for (int i=n-1;i>=0;i--)
	{
		for (int j=1;j<LG;j++)
		{
			calc[i][j]=calc[min(n,calc[i][j-1].first+1)][j-1];
		}
	}
	cin>>q;
	while (q--)
	{
		int l,r;
		cin>>l>>r;
		l--;r--;
		int ans=0;
		for (int i=LG-1;i>=0;i--)
		{
			if (calc[l][i].first<=r)
			{
				ans+=(1<<i);
				l=calc[l][i].first+1;
			}
		}
		cout<<ans<<endl;
	}
}
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t=1;
    for (int i=1;i<=t;i++)
    {
        solve();
    }
}

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