제출 #1225701

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

sumzero

#include <iostream>
#include <map>
#include <vector>
#include <deque>
#include <set>
#include <algorithm>
using namespace std;
#define int long long
int const N=5e3+10;
int par[N],nx[N],mn[N],pre[N],ans[N],ans1[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);
	while (st[u].size()&&st[u][0]<nx[v]&&en[u][0]>nx[v])
	{
		st[u].pop_front();
		en[u].pop_front();
	}
	if ((st[u].size()&&st[u][0]>nx[v])||st[u].size()==0)
	{
		st[u].push_front(v);
		en[u].push_front(nx[v]);
		par[v]=u;
	}
	else
		merge(v,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;
			set<int>s;
			s.insert(0);
			int y=0;
			ans1[k]=0;
			for (int l=i;l<=j;l++)
			{
				y+=a[l];
				if (s.find(y)!=s.end())
				{
					ans1[k]++;
					s={};
					y=0;
				}
				s.insert(y);
			}
		}
	}
	for (int i=0;i<q;i++)
	{
		if (ans1[i]>ans[i])
			exit(-1);
		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: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39