제출 #1225691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225691		Muhammad_Aneeq	Sum Zero (RMI20_sumzero)	C++20	0 / 100	9 ms	7488 KiB

sumzero

#include <iostream>
#include <map>
#include <vector>
#include <deque>
#include <set>
#include <algorithm>
using namespace std;
int const N=5e3+10;
int par[N],nx[N],mn[N],pre[N],ans[N];
deque<int>st[N],en[N];
vector<pair<int,int>>qu[N]={};
int root(int n)
{
	return (par[n]==n?n:(par[n]=root(par[n])));
}
set<pair<int,int>>s;
void merge(int u,int v)
{
	u=root(u);
	v=root(v);
	par[v]=u;
	if (st[u].size())
	{
		s.erase({en[u][0],st[u][0]});
	}
	st[u].push_front(v);
	en[u].push_front(nx[v]);
}
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++)
		par[i]=i;
	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;
	}
	cin>>q;
	for (int i=0;i<q;i++)
	{
		int l,r;
		cin>>l>>r;
		l--;r--;
		qu[l].push_back({r,i});
	}
	mn[n]=n+10;
	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 (f>=n)
				merge(i,i);
			else
			{
				int g=pre[f];
				merge(g,i);
			}
		}
		for (auto [j,k]:qu[i])
		{
			if (s.size()==0)
			{
				ans[k]=0;
				continue;
			}
			int f=(*begin(s)).second;
			f=root(f);
			int z=upper_bound(begin(en[f]),end(en[f]),j)-begin(en[f]);
			ans[k]=z;
		}
	}
	for (int i=0;i<q;i++)
		cout<<ans[i]<<endl;
}
int 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: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39