oj.uz

답안 #722347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
722347 2023-04-11T20:02:07 Z groshi 중앙값 배열 (balkan11_medians) C++17
100 / 100
 163 ms 16052 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,tree_order_statistics_node_update>
new_data_set;
int b[300000];
int wynik[300000];
set<int> mam;
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    new_data_set secik;
    int n;
    cin>>n;
    for(int i=1;i<=2*n-1;i++)
        mam.insert(i);
    for(int i=1;i<=n;i++)
        cin>>b[i];
    int jestem=1;
    for(int i=1;i<=n;i++)
    {
        int mniejszych=i-1;
        int wiekszych=i-1;
        mniejszych-=(secik.order_of_key(b[i]));
        wiekszych-=(secik.size()-secik.order_of_key(b[i]+1));
        auto it=mam.begin();
        int ile1=mniejszych,ile2=wiekszych;
        while(mniejszych>0)
        {
            wynik[jestem]=*it;
            secik.insert(*it);
            it++;
            mniejszych--;
            jestem++;
        }
        it=mam.end();
        it--;
        while(wiekszych>0)
        {
            wynik[jestem]=*it;
            secik.insert(*it);
            it--;
            wiekszych--;
            jestem++;
        }
        while(ile1)
        {
            it=mam.begin();
            mam.erase(*it);
            ile1--;
        }
        while(ile2)
        {
            it=mam.end();
            it--;
            mam.erase(*it);
            ile2--;
        }
        if(mam.find(b[i])!=mam.end())
        {
            mam.erase(b[i]);
            secik.insert(b[i]);
            wynik[jestem]=b[i];
            jestem++;
        }
    }
    for(int i=1;i<=n*2-1;i++)
        cout<<wynik[i]<<" ";
    return 0;
}

Subtask #1
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 2 ms 468 KB Output is correct

Subtask #2
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 724 KB Output is correct
2 Correct 6 ms 980 KB Output is correct
3 Correct 11 ms 1484 KB Output is correct
4 Correct 31 ms 2844 KB Output is correct
5 Correct 58 ms 5196 KB Output is correct
6 Correct 104 ms 10284 KB Output is correct
7 Correct 163 ms 16052 KB Output is correct