# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
217662 | KoalaMuch | medians (balkan11_medians) | C++14 | 120 ms | 13560 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int f[N];
set< int > s;
int ans[N];
int a[N];
int cur = 1;
void upd(int i)
{
while(i<N) ++f[i],i+=i&-i;
}
int get(int i,int ret = 0)
{
while(i) ret+=f[i],i-=i&-i;
return ret;
}
void add(int v)
{
ans[cur] = v;
s.erase(s.find(v));
upd(v+1);
cur++;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<2*n;i++) s.insert(i);
for(int i=1;i<=n;i++)
{
if(s.count(a[i])) add(a[i]);
if(get(a[i])!=i-1) add(*s.begin());
if(cur-get(a[i]+1)!=i) add(*(--s.end()));
}
for(int i=1;i<2*n;i++) printf("%d ",ans[i]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |