SMMR-246: Median (priority queue)

#include <bits/stdc++.h>

using namespace std;

void prt(priority_queue <int> one, priority_queue <int, vector <int>, greater <int>> two){
    while(one.size() > 0){
        printf("%d ", one.top());
        one.pop();
    }
    printf("\n");
    while(two.size() > 0){
        printf("%d ", two.top());
        two.pop();
    }
    printf("\n");
}

int main(){

    int n;
    scanf("%d", &n);

    priority_queue <int> one;
    priority_queue <int, vector <int>, greater <int>> two;

    int x1, x2;
    scanf("%d%d", &x1, &x2);
    printf("%d %d ", x1, (x1+x2)/2);
    if(x1 < x2){
        one.push(x1);
        two.push(x2);
    }
    else{
        one.push(x2);
        two.push(x1);
    }

    for(int i=3;i<=n;i++){
        int x;
        scanf("%d", &x);
        if(i % 2 == 1){
            if(x < two.top()){
                one.push(x);
            }
            else {
                one.push(two.top());
                two.pop();
                two.push(x);
            }
        }
        else {
            if(x > one.top()) two.push(x);
            else {
                two.push(one.top());
                one.pop();
                one.push(x);
            }
        }
        if(i % 2 == 1) printf("%d ", one.top());
        else printf("%d ", (one.top() + two.top()) / 2);
    }

    return 0;
}