Submission #372805

#TimeUsernameProblemLanguageResultExecution timeMemory
372805iliccmarkomedians (balkan11_medians)C++14
0 / 100
138 ms5152 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(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 main() { ios cin>>n; for(int i = 0;i<n;i++) cin>>b[i]; update(0, 0, 2*n, b[0]); a.pb(b[0]); int l = 1; if(b[0]==1) l++; int r = 2*n-1; if(b[0]==2*n-1) r--; for(int i = 1;i<n;i++) { int x = b[i]; int cl = get_sum(0, 0, x-1, 0, 2*n); int cr = get_sum(0, x+1, 2*n, 0, 2*n); if(l==x) l++; if(r==x) r--; //cout<<cl<<" "<<cr<<" "; if(cl==cr) { //cout<<i<<" 1"<<endl; while(get_sum(0, l, l, 0, 2*n)) l++; while(get_sum(0, r, r, 0, 2*n)) r--; a.pb(l); a.pb(r); update(0, 0, 2*n, l); update(0, 0, 2*n, r); l++; r--; while(get_sum(0, l, l, 0, 2*n)) l++; while(get_sum(0, r, r, 0, 2*n)) r--; } else if(cl>cr) { if(!get_sum(0, x, x, 0, 2*n)) { //cout<<i<<" 2"<<endl; while(get_sum(0, l, l, 0, 2*n)) l++; while(get_sum(0, r, r, 0, 2*n)) r--; a.pb(x); a.pb(r); update(0, 0, 2*n, x); update(0, 0, 2*n, r); r--; while(get_sum(0, r, r, 0, 2*n)) r--; } else { //cout<<i<<" 3"<<endl; while(get_sum(0, l, l, 0, 2*n)) l++; while(get_sum(0, r, r, 0, 2*n)) r--; a.pb(r); update(0, 0, 2*n, r); r--; while(get_sum(0, r, r, 0, 2*n)) r--; update(0, 0, 2*n, r); a.pb(r); r--; while(get_sum(0, r, r, 0, 2*n)) r--; } } else { if(!get_sum(0, x, x, 0, 2*n)) { //cout<<i<<" 4"<<endl; while(get_sum(0, l, l, 0, 2*n)) l++; while(get_sum(0, r, r, 0, 2*n)) r--; a.pb(x); a.pb(l); update(0, 0, 2*n, x); update(0, 0, 2*n, l); l++; while(get_sum(0, l, l, 0, 2*n)) l++; } else { //cout<<i<<" 5"<<endl; while(get_sum(0, l, l, 0, 2*n)) l++; while(get_sum(0, r, r, 0, 2*n)) r--; a.pb(l); update(0, 0, 2*n, l); l++; while(get_sum(0, l, l, 0, 2*n)) l++; update(0, 0, 2*n, l); a.pb(l); l++; while(get_sum(0, l, l, 0, 2*n)) l++; } } } for(int x : a) cout<<x<<" "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...