제출 #1225695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225695		MuhammadSaram	Sum Zero (RMI20_sumzero)	C++20	61 / 100	374 ms	36012 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

#define ll long long

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

int nxt[M][3],ans[M],a[M];
map<ll,vector<int>> ind;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n;
	cin>>n;
	ll su=0;
	ind[su].push_back(0);
	for (int i=1;i<=n;i++)
		cin>>a[i],su+=a[i],ind[su].push_back(i);
	for (auto [i,v]:ind)
		reverse(ind[i].begin(),ind[i].end()),ind[i].shrink_to_fit();
	set<int> se={n+1};
	for (auto [x,v]:ind)
		if (v.size()>1)
			se.insert(v[v.size()-2]);
	su=0;
	for (int i=1;i<=n+1;su+=a[i],i++)
	{
		nxt[i][2]=*se.begin();
		ind[su].pop_back();
		int m=ind[su].size();
		if (m)
			se.erase(ind[su].back());
		if (m>1)
			se.insert(ind[su][m-2]);
	}
	ind.clear(),se.clear();
	nxt[n+2][2]=n+1;
	int q;
	cin>>q;
	int l[q],r[q];
	for (int i=0;i<q;i++)
		cin>>l[i]>>r[i];
	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[l[i]][lim%2]<=r[i])
				ans[i]+=(1<<lim),l[i]=nxt[l[i]][lim%2]+1;
	}
	for (int i=0;i<q;i++)
		cout<<ans[i]<<'\n';
	
	return 0;
}

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