Submission #1866697

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define MAXI 200020
#define u(x, a, b) for(ll x = a; x < b; x++)
#define d(x, a, b) for(ll x = a; x > b; x--)

pair<ll, ll> st0[MAXI][20];// 0 mod 2
pair<ll, ll> st1[MAXI][20];// 1 mod 2

pair<ll, ll> queryst0(ll le, ll ri){
    int k = log2(ri-le);
    ll ans = min(st0[le][k].first, st0[ri-(1 << k)][k].first); // <-- for query [l, r]
    ll pos;
    if(ans == st0[le][k].first){
        pos = st0[le][k].second;
    }
    else{
        pos = st0[ri-(1 << k)][k].second;
    }
    pair<ll, ll> t = make_pair(ans, pos);
    return t;
}

pair<ll, ll> queryst1(ll le, ll ri){
    int k = log2(ri-le);
    ll ans = min(st1[le][k].first, st1[ri-(1 << k)][k].first); // <-- for query [l, r]
    ll pos;
    if(ans == st1[le][k].first){
        pos = st1[le][k].second;
    }
    else{
        pos = st1[ri-(1 << k)][k].second;
    }
    pair<ll, ll> t = make_pair(ans, pos);
    return t;
}

deque< pair<ll, ll> > greedy(vector<ll> in, ll le, ll ri){
    deque< pair<ll, ll> > ans;
    ll min1, tar1, min2, tar2;

    if(le >= ri){
        ans.push_back(make_pair(MAXI, MAXI));
        return ans;
    }

    if(le%2){
        pair<ll, ll> v = queryst1(le, ri);
        tar1 = v.second;
        min1 = v.first;
    }
    else{
        pair<ll, ll> v = queryst0(le, ri);
        tar1 = v.second;
        min1 = v.first;
    }

    if((tar1+1)%2){
        pair<ll, ll> v = queryst1(tar1+1, ri);
        tar2 = v.second;
        min2 = v.first;
    }
    else{
        pair<ll, ll> v = queryst0(tar1+1, ri);
        tar2 = v.second;
        min2 = v.first;
    }
    ans.push_back(make_pair(min1, min2));
    deque< pair<ll, ll> > a1 = greedy(in, le, tar1), a2 = greedy(in, tar1+1, tar2), a3 = greedy(in, tar2+1, ri);
    ll y = MAXI;
    if(!a1.empty()){
        y = min(a1[0].first, y);
    }
    if(!a2.empty()){
        y = min(a2[0].first, y);
    }
    if(!a3.empty()){
        y = min(a3[0].first, y);
    }
    while(y < MAXI){
        if(!a1.empty()){
            if(y == a1[0].first){
                ans.push_back(a1[0]);
                a1.pop_front();
            }
        }
        if(!a2.empty()){
            if(y == a2[0].first){
                ans.push_back(a2[0]);
                a2.pop_front();
            }
        }
        if(!a3.empty()){
            if(y == a3[0].first){
                ans.push_back(a3[0]);
                a3.pop_front();
            }
        }
        y = MAXI;
        if(!a1.empty()){
            y = min(a1[0].first, y);
        }
        if(!a2.empty()){
            y = min(a2[0].first, y);
        }
        if(!a3.empty()){
            y = min(a3[0].first, y);
        }
    }

    return ans;
}

int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    ll n, temp;
    cin >> n;
    vector<ll> arr;
    u(three, 0, n){
        cin >> temp;
        arr.push_back(temp);
    }
    //sparse table
    int pwr = log2(n);
    for(int j = 0;j <= pwr;j++){
        for(int i = 0; i < n;i ++){
            if(i + (1 << j) - 1 < n){
                pair<ll, ll> imax = make_pair(MAXI, i);
                pair<ll, ll> curi = make_pair(arr[i], i);
                ll minst0 = min(st0[i][j-1].first, st0[i + (1 << (j-1))][j-1].first), posmin0;
                ll minst1 = min(st1[i][j-1].first, st1[i + (1 << (j-1))][j-1].first), posmin1;
                if(minst0 == st0[i][j-1].first){
                    posmin0 = st0[i][j-1].second;
                }
                else{
                    posmin0 = st0[i + (1 << (j-1))][j-1].second;
                }
                if(minst1 == st1[i][j-1].first){
                    posmin1 = st1[i][j-1].second;
                }
                else{
                    posmin1 = st1[i + (1 << (j-1))][j-1].second;
                }
                pair<ll, ll> cur0 = make_pair(minst0, posmin0);
                pair<ll, ll> cur1 = make_pair(minst1, posmin1);
                st0[i][j] = (j ? cur0 : (i%2==1 ? imax : curi));//if j = 0, i%2 = 0 then st0[i][0] = arr[i]
                st1[i][j] = (j ? cur1 : (i%2==1 ? curi : imax));//opposite for st1
            }
            else{
                st0[i][j] = make_pair(MAXI, MAXI);
                st1[i][j] = make_pair(MAXI, MAXI);
            }
        }
    }
    deque< pair<ll, ll> > fin = greedy(arr, 0, n);
    u(three, 0, n/2){
        cout << fin[three].first << ' ' << fin[three].second << ' ';
    }
}

Submission Info

Judge Result