Submission #404859

#	Time	Username	Problem	Language	Result	Execution time	Memory
404859		Pyqe	Sum Zero (RMI20_sumzero)	C++11	61 / 100	579 ms	24180 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

int n,nn=0,pr[400069][10];
map<long long,int> ls;
pair<int,int> a[400069];

int main()
{
	int t,rr,i,j,k,l,sz,z;
	long long sm=0;
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&k);
		sm+=k;
		if(ls[sm]||!sm)
		{
			nn++;
			a[nn]={ls[sm]+1,i};
		}
		ls[sm]=i;
	}
	sort(a+1,a+nn+1);
	sz=nn;
	nn=0;
	for(i=1;i<=sz;i++)
	{
		for(;nn&&a[nn].sc>=a[i].sc;nn--);
		nn++;
		a[nn]=a[i];
	}
	a[nn+1]={n+1,n+1};
	for(i=0;i<10;i++)
	{
		pr[nn+1][i]=nn+1;
	}
	for(i=nn;i;i--)
	{
		pr[i][0]=upper_bound(a+1,a+nn+1,mp(a[i].sc,n+1))-a;
		for(j=1;j<10;j++)
		{
			pr[i][j]=pr[pr[pr[pr[i][j-1]][j-1]][j-1]][j-1];
		}
	}
	scanf("%d",&t);
	for(rr=0;rr<t;rr++)
	{
		scanf("%d%d",&k,&l);
		k=lower_bound(a+1,a+nn+1,mp(k,0))-a;
		z=0;
		if(a[k].sc<=l)
		{
			z++;
			for(i=9;i+1;i--)
			{
				for(;a[pr[k][i]].sc<=l;k=pr[k][i])
				{
					z+=1<<i*2;
				}
			}
		}
		printf("%d\n",z);
	}
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
sumzero.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d",&k);
      |   ~~~~~^~~~~~~~~
sumzero.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d",&t);
      |  ~~~~~^~~~~~~~~
sumzero.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d",&k,&l);
      |   ~~~~~^~~~~~~~~~~~~~

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