oj.uz

답안 #404871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404871 2021-05-15T07:59:54 Z Pyqe Sum Zero (RMI20_sumzero) C++11
100 / 100
 562 ms 16676 KB 
#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

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.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 102 ms 2628 KB Output is correct
8 Correct 108 ms 3128 KB Output is correct
9 Correct 101 ms 2492 KB Output is correct
10 Correct 106 ms 2628 KB Output is correct
11 Correct 126 ms 3152 KB Output is correct
12 Correct 98 ms 2500 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 5 ms 332 KB Output is correct
3 Correct 4 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 102 ms 2628 KB Output is correct
8 Correct 108 ms 3128 KB Output is correct
9 Correct 101 ms 2492 KB Output is correct
10 Correct 106 ms 2628 KB Output is correct
11 Correct 126 ms 3152 KB Output is correct
12 Correct 98 ms 2500 KB Output is correct
13 Correct 522 ms 10304 KB Output is correct
14 Correct 562 ms 12240 KB Output is correct
15 Correct 529 ms 9668 KB Output is correct
16 Correct 509 ms 10076 KB Output is correct
17 Correct 540 ms 12100 KB Output is correct
18 Correct 508 ms 16676 KB Output is correct