Submission #1227879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227879		MuhammadSaram	Sum Zero (RMI20_sumzero)	C++20	100 / 100	215 ms	15144 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int M = 4e5+1, lg = 19;

int nxt[M+2][3],a[M];
pair<int,int> ind[M];
vector<ll> v;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n;
	cin>>n;
	ll su=0;
	v={0};
	for (int i=1;i<=n;i++)
		cin>>a[i],su+=a[i],v.push_back(su);
	int mn=n+1;
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	for (int i=0;i<v.size();i++) ind[i]={-1,-1};
	for (int i=n+1;i>=1;i--)
	{
		int id=lower_bound(v.begin(),v.end(),su)-begin(v);
		ind[id].second=ind[id].first,ind[id].first=i-1;
		if (~ind[id].second) mn=min(mn,ind[id].second);
		nxt[i][2]=mn;
		su-=a[i-1];
	}
	nxt[n+2][2]=n+1;
	int q;
	cin>>q;
	for (int i=0;i<q;i++)
		cin>>ind[i].first>>ind[i].second,a[i]=0;
	for (int lim=lg-1;lim>=0;lim--)
	{
		for (int i=1;i<=n+2;i++)
			nxt[i][0]=nxt[i][2];
		for (int p=1;p<=lim;p++)
			for (int i=1;i<=n+2;i++)
				nxt[i][p%2]=nxt[nxt[i][1-p%2]+1][1-p%2];
		for (int i=0;i<q;i++)
			if (nxt[ind[i].first][lim%2]<=ind[i].second)
				a[i]+=(1<<lim),ind[i].first=nxt[ind[i].first][lim%2]+1;
	}
	for (int i=0;i<q;i++)
		cout<<a[i]<<'\n';
	
	return 0;
}

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