Submission #372817

#TimeUsernameProblemLanguageResultExecution timeMemory
372817iliccmarkomedians (balkan11_medians)C++14
5 / 100
119 ms5732 KiB
#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<r) 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)) 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); 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...