oj.uz

답안 #373262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373262 2021-03-04T00:23:39 Z iliccmarko 중앙값 배열 (balkan11_medians) C++14
0 / 100
 139 ms 6884 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define input(n, v) {for(int i = 0;i<n;i++) cin>>v[i];}
#define output(n, v) {for(int i = 0;i<n;i++) cout<<v[i]<<" "; cout<<endl;}
#define single_case solve();
#define line cout<<"------------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); }
const int N = 2e5 + 50;
int seg[4*N];
int n;
int b[N];
vector<int> a;

void update(int node, int l, int r, int pos)
{
    if(l==r){
        seg[node] = 1;
        return;
    }
    int mid = (l+r)/2;
    if(pos>mid) update(node*2+2, mid+1, r, pos);
    else update(node*2+1, l, mid, pos);
    seg[node] = seg[node*2+1] + seg[node*2+2];
}

int get_sum(int node, int l, int r, int i, int j)
{
    if(l>r) return 0;
    if(i>r||j<l) return 0;
    if(i>=l&&j<=r) return seg[node];
    int mid = (i+j)/2;
    return get_sum(node*2+1, l, r, i, mid) + get_sum(node*2+2, l, r, mid+1, j);
}

int prvanula(int node, int l, int r)
{
    if(l==r){
        if(seg[node]) return -1;
        else return l;
    }
    int mid = (l+r)/2;
    if(seg[node*2+1]==mid-l+1) return prvanula(node*2+2, mid+1, r);
    else return prvanula(node*2+1, l, mid);
}

int poslednjanula(int node, int l, int r)
{
    if(l==r)
    {
        if(seg[node]) return -1;
        else return l;
    }
    int mid = (l+r)/2;
    if(seg[node*2+2]==r-(mid+1)+1) return poslednjanula(node*2+1, l, mid);
    else return poslednjanula(node*2+2, mid+1, r);
}

int main()
{
    ios
    cin>>n;
    for(int i = 0;i<n;i++) cin>>b[i];
    update(0, 1, 2*n-1, b[0]);
    a.pb(b[0]);
    for(int i = 1;i<n;i++)
    {
        int x = b[i];
        int s = 0;
        if(get_sum(0, x, x, 1, 2*n-1)==0) a.pb(x), update(0, 1, 2*n-1, x), s = 1;
        int cl = get_sum(0, 1, x-1, 1, 2*n-1);
        int cr = get_sum(0, x+1, 2*n-1, 1, 2*n-1);
        cout<<cl<<" "<<cr<<endl;
        if(cr>cl)
        {
            if(s)
            {
                //cout<<1<<" "<<endl;
                int l = prvanula(0, 1, 2*n-1);
                a.pb(l);
                update(0, 1, 2*n-1, l);
            }
            else
            {
                //cout<<2<<" "<<endl;
                int l = prvanula(0, 1, 2*n-1);
                a.pb(l);
                update(0, 1, 2*n-1, l);
                l = prvanula(0, 1, 2*n-1);
                a.pb(l);
                update(0, 1, 2*n-1, l);
            }
        }
        else if(cl>cr)
        {
            if(s)
            {
                //cout<<3<<" "<<endl;
                int r = poslednjanula(0, 1, 2*n-1);
                a.pb(r);
                update(0, 1, 2*n-1, r);
            }
            else
            {
                //cout<<4<<" "<<endl;
                int r = poslednjanula(0, 1, 2*n-1);
                a.pb(r);
                update(0, 1, 2*n-1, r);
                r = poslednjanula(0, 1, 2*n-1);
                a.pb(r);
                update(0, 1, 2*n-1, r);
            }
        }
        else
        {
            //cout<<5<<" "<<endl;
            int l = prvanula(0, 1, 2*n-1);
            int r = poslednjanula(0, 1, 2*n-1);
            //cout<<l<<" "<<r<<"-----"<<endl;
            a.pb(l);
            a.pb(r);
            update(0, 1, 2*n-1, l);
            update(0, 1, 2*n-1, r);
        }
    }

    for(int x : a)
        cout<<x<<" ";




    return 0;
}

Subtask #1
0.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 19]
2 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 39]
3 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 59]
4 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 79]
5 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 99]
6 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 119]
7 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 139]
8 Incorrect 1 ms 384 KB Integer 0 violates the range [1, 159]
9 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 179]
10 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 199]
11 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 599]
12 Incorrect 1 ms 364 KB Integer 0 violates the range [1, 1199]
13 Incorrect 2 ms 364 KB Integer 0 violates the range [1, 1999]

Subtask #2
0.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 492 KB Integer 0 violates the range [1, 3999]
2 Incorrect 5 ms 620 KB Integer 0 violates the range [1, 7999]
3 Incorrect 10 ms 876 KB Integer 0 violates the range [1, 15999]
4 Incorrect 22 ms 1388 KB Integer 0 violates the range [1, 31999]
5 Incorrect 42 ms 2416 KB Integer 0 violates the range [1, 63999]
6 Incorrect 93 ms 4312 KB Integer 0 violates the range [1, 127999]
7 Incorrect 139 ms 6884 KB Integer 0 violates the range [1, 199999]