Submission #146025

#	Time	Username	Problem	Language	Result	Execution time	Memory
146025		TadijaSebez	medians (balkan11_medians)	C++11	100 / 100	94 ms	8312 KiB

medians

#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 (stderr)

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 / 65
• Subtask 2: 35 / 35