Submission #404871

#	Time	Username	Problem	Language	Result	Execution time	Memory
404871		Pyqe	Sum Zero (RMI20_sumzero)	C++11	100 / 100	562 ms	16676 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][5];
pair<long long,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;
		a[i]={sm,i};
	}
	a[n+1]={0,0};
	sort(a+1,a+n+2);
	for(i=1;i<=n;i++)
	{
		if(a[i].fr==a[i+1].fr)
		{
			nn++;
			a[nn]={a[i].sc+1,a[i+1].sc};
		}
	}
	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<5;i++)
	{
		pr[nn+1][i]=nn+1;
	}
	for(i=nn;i;i--)
	{
		pr[i][0]=upper_bound(a+1,a+nn+1,mp((long long)a[i].sc,n+1))-a;
		for(j=1;j<5;j++)
		{
			pr[i][j]=pr[pr[pr[pr[pr[pr[pr[pr[i][j-1]][j-1]][j-1]][j-1]][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((long long)k,0))-a;
		z=0;
		if(a[k].sc<=l)
		{
			z++;
			for(i=4;i+1;i--)
			{
				for(;a[pr[k][i]].sc<=l;k=pr[k][i])
				{
					z+=1<<i*3;
				}
			}
		}
		printf("%d\n",z);
	}
}

Compilation message (stderr)

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

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