Submission #1867034


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

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

vector<ll> in;
deque< pair< pair<ll, ll>, ll> > ans;// <num,num>,lvl

bool isbefore(ll a, ll b){ //does a have to be before b
    while(b < a){
        b*=2;
        b++;
    }
    return (a==b);
}

bool comp(pair< pair<ll, ll>, ll> a, pair< pair<ll, ll>, ll> b){ //if true,  go to front
    if(isbefore(b.second, a.second)){
        return true;
    }
    else if(isbefore(a.second, b.second)){
        return false;
    }
    else{
        return (a.first.first < b.first.first);
    }
}

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;
}

void greedy(ll le, ll ri, ll lvl){
    ll min1, tar1, min2, tar2;

    if(le >= ri){
        return;
    }

    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;
    }
    pair<ll, ll> a[3];
    greedy(le, tar1, 2*lvl);
    greedy(tar1+1, tar2, 2*lvl+1);
    greedy(tar2+1, ri, 2*lvl);
    ans.push_back( make_pair( make_pair(min1, min2), lvl) );
    return;
}

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

    ll n, temp;
    cin >> n;
    u(three, 0, n){
        cin >> temp;
        in.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(in[i], i), cur0, cur1;
                if(j){
                    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;
                    }
                    cur0 = make_pair(minst0, posmin0);
                    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);
            }
        }
    }
    greedy(0, n, 1);
    sort(ans.begin(), ans.end(), comp);
    u(three, 0, n/2){
        cout << ans[three].first.first << ' ' << ans[three].first.second << ' ';
    }
}

Submission Info

Submission Time
Task E - Young Maids
User vjudge1
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4047 Byte
Status WA
Exec Time 2105 ms
Memory 140144 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 3
AC × 5
WA × 12
TLE × 6
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt
Case Name Status Exec Time Memory
0_00.txt AC 4 ms 2560 KB
0_01.txt AC 2 ms 2304 KB
0_02.txt AC 2 ms 2304 KB
1_00.txt AC 2 ms 2304 KB
1_01.txt AC 2 ms 2304 KB
1_02.txt TLE 2104 ms 140144 KB
1_03.txt TLE 2105 ms 140144 KB
1_04.txt TLE 2105 ms 140144 KB
1_05.txt WA 243 ms 130544 KB
1_06.txt WA 246 ms 130544 KB
1_07.txt WA 584 ms 130544 KB
1_08.txt WA 242 ms 130544 KB
1_09.txt TLE 2105 ms 140144 KB
1_10.txt TLE 2104 ms 137456 KB
1_11.txt TLE 2104 ms 136816 KB
1_12.txt WA 237 ms 128112 KB
1_13.txt WA 314 ms 130416 KB
1_14.txt WA 241 ms 130416 KB
1_15.txt WA 299 ms 130416 KB
1_16.txt WA 304 ms 130416 KB
1_17.txt WA 245 ms 130416 KB
1_18.txt WA 256 ms 130416 KB
1_19.txt WA 309 ms 130416 KB