Submission #1225760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225760		Muhammad_Aneeq	Sum Zero (RMI20_sumzero)	C++20	100 / 100	481 ms	15344 KiB

sumzero

#include <iostream>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
int const N=4e5+2,lg=19;
int ans[N],l[N],r[N];
int calc[N][3]={};
inline void solve()
{
	int n,q;
	cin>>n;
	vector<pair<int,int>>s;
	s.push_back({0,-1});
	for (int i=0;i<n;i++)
		cin>>ans[i];
	long long mn=0;
	for (int i=0;i<n;i++)
	{
		r[i]=-1;
		mn+=ans[i];
		s.push_back({mn,i});
	}
	sort(begin(s),end(s));
	for (int i=0;i<s.size();i++)
	{
		int j=i;
		while (j<s.size()&&s[j].first==s[i].first)
			j++;
		for (;i+1<j;i++)
			r[s[i].second+1]=s[i+1].second;
		i=j-1;
	}
	s={};
	for (int j=0;j<3;j++)
		calc[n][j]=calc[n+1][j]=n;
	r[n]=n+10;
	mn=n;
	for (int i=n-1;i>=0;i--)
	{
		int fr=r[i];
		r[i]=r[i+1];
		if (fr!=-1)
		{
			int f=r[fr+1];
			r[i]=min(r[i],fr);
			mn=min(mn,1ll*fr);
		}
		calc[i][2]=mn;
	}
	cin>>q;
	for (int i=1;i<=q;i++)
	{
		cin>>l[i]>>r[i];
		l[i]--;r[i]--;
		ans[i]=0;
	}
	for (int cur=lg-1;cur>=0;cur--)
	{		
		for (int j=0;j<n;j++)
			calc[j][0]=calc[j][2];
		for (int i=1;i<=cur;i++)
		{
			for (int j=0;j<n;j++)
				calc[j][1]=calc[min(n,calc[j][0]+1)][0];
			for (int j=0;j<n;j++)
				calc[j][0]=calc[j][1];
		}
		for (int i=1;i<=q;i++)
		{
			if (calc[l[i]][0]<=r[i])
			{
				ans[i]+=(1<<cur);
				l[i]=calc[l[i]][0]+1;
			}
		}
	}
	for (int i=1;i<=q;i++)
		cout<<ans[i]<<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: 39 / 39
• Subtask 3: 39 / 39