oj.uz

Submission #146025

# Submission time Handle Problem Language Result Execution time Memory
146025 2019-08-21T15:40:00 Z TadijaSebez medians (balkan11_medians) C++11
100 / 100
 94 ms 8312 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=200050;
const int M=2*N;
bool was[N];
int ls[M],rs[M],tsz,root,sum[M];
void Set(int &c, int ss, int se, int qi)
{
	if(!c) c=++tsz;
	sum[c]++;
	if(ss==se) return;
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi);
	else Set(rs[c],mid+1,se,qi);
}
int Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe || !c) return 0;
	if(qs<=ss && qe>=se) return sum[c];
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
int a[N],b[N],l,r,sz;
void Add(int i)
{
	was[i]=1;
	Set(root,1,N,i);
	a[++sz]=i;
}
int main()
{
	int n;
	scanf("%i",&n);
	for(int i=1;i<=n;i++) scanf("%i",&b[i]);
	l=1;r=n*2-1;
	Add(b[1]);
	for(int i=2;i<=n;i++)
	{
		int L=Get(root,1,N,1,b[i]-1);
		int R=Get(root,1,N,b[i]+1,N);
		for(int j=0;j<2;j++)
		{
			if(!was[b[i]]) Add(b[i]);
			else
			{
				while(was[l]) l++;
				while(was[r]) r--;
				if(L<R) Add(l),L++;
				else Add(r),R++;
			}
		}
	}
	for(int i=1;i<=sz;i++) printf("%i ",a[i]);
	return 0;
}

Compilation message

medians.cpp: In function 'void Set(int&, int, int, int)':
medians.cpp:12:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
medians.cpp: In function 'int Get(int, int, int, int, int)':
medians.cpp:20:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
medians.cpp: In function 'int main()':
medians.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
medians.cpp:34:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&b[i]);
                        ~~~~~^~~~~~~~~~~~

Subtask #1
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 424 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 6 ms 632 KB Output is correct
3 Correct 10 ms 888 KB Output is correct
4 Correct 17 ms 1528 KB Output is correct
5 Correct 31 ms 2808 KB Output is correct
6 Correct 60 ms 5368 KB Output is correct
7 Correct 94 ms 8312 KB Output is correct