Submission #2707132


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using PP = pair<int, P>;
using PPP = pair<P, P>;
int N;
vector<int> p;
constexpr int INF = 300000;

class segTree
{
    int num;
    vector<PPP> v;
    void update(int i)
    {
        P tmp_odd = min(v[2 * i + 1].first, v[2 * i + 2].first);
        P tmp_even = min(v[2 * i + 1].second, v[2 * i + 2].second);
        v[i] = make_pair(tmp_odd, tmp_even);
    }
public:
    segTree(){ ;}
    segTree(vector<int> v_init, P DEFAULT)
    {
        num = v_init.size();
        int tmp = 1;
        while (tmp<(int)v_init.size()) tmp*=2;
        tmp *= 2;
        v.resize(tmp, make_pair(DEFAULT, DEFAULT));
        for (int i = 0; i < num; i++)
        {
            if (i&1) v[tmp/2-1+i] = make_pair(DEFAULT, make_pair(v_init[i], i));
            else v[tmp/2-1+i] = make_pair(make_pair(v_init[i], i), DEFAULT);
        }
        for (int i = tmp / 2 - 2; i >= 0; i--) update(i);
    }
    PPP query_min(int begin, int end, int node, int l, int r)
    {
        if (r <= begin || l >= end) return make_pair(make_pair(INF, INF), make_pair(INF, INF));
        if (begin<=l && end>=r) return v[node];

        PPP v_l = query_min(begin, end, 2 * node + 1, l, (l + r) / 2);
        PPP v_r = query_min(begin, end, 2 * node + 2, (l + r) / 2, r);
        return make_pair(min(v_l.first, v_r.first), min(v_l.second, v_r.second));
    }
    P query_min_odd(int begin, int end)
    {
        if (begin % 2 == 0)
        {
            return query_min(begin, end, 0, 0, (int)v.size() / 2).first;
        }
        else
        {
            return query_min(begin, end, 0, 0, (int)v.size() / 2).second;
        }
    }
};

int main()
{
    cin >> N;
    p.resize(N);
    for (auto &i : p) cin >> i;

    segTree tree(p, make_pair(INF, INF));

    priority_queue<PPP, vector<PPP>, greater<PPP> > que;
    que.push(make_pair(tree.query_min_odd(0, N), make_pair(0, N)));

    vector<int> res;
    while (!que.empty())
    {
        PPP q = que.top();
        que.pop();

        int val1 = q.first.first;
        int arg1 = q.first.second;
        P range = q.second;
        P val2cand = tree.query_min_odd(arg1 + 1, range.second);
        int arg2 = val2cand.second;
        res.push_back(val1); res.push_back(val2cand.first);
        if (range.first < arg1) que.push(make_pair(tree.query_min_odd(range.first, arg1), make_pair(range.first, arg1)));
        if (arg1 + 1 < arg2) que.push(make_pair(tree.query_min_odd(arg1+1, arg2), make_pair(arg1+1, arg2)));
        if (arg2 + 1 < range.second) que.push(make_pair(tree.query_min_odd(arg2+1, range.second), make_pair(arg2+1, range.second)));
    }
    for (auto v : res) cout << v << " ";
    return 0;
}

Submission Info

Submission Time
Task E - Young Maids
User hitonanode
Language C++14 (GCC 5.4.1)
Score 800
Code Size 2797 Byte
Status AC
Exec Time 146 ms
Memory 12912 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 23
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 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 1 ms 256 KB
1_02.txt AC 127 ms 12272 KB
1_03.txt AC 110 ms 12272 KB
1_04.txt AC 140 ms 12272 KB
1_05.txt AC 144 ms 12784 KB
1_06.txt AC 146 ms 12528 KB
1_07.txt AC 142 ms 12912 KB
1_08.txt AC 144 ms 12912 KB
1_09.txt AC 114 ms 12272 KB
1_10.txt AC 142 ms 12272 KB
1_11.txt AC 137 ms 12272 KB
1_12.txt AC 141 ms 12684 KB
1_13.txt AC 146 ms 12788 KB
1_14.txt AC 144 ms 12796 KB
1_15.txt AC 146 ms 12788 KB
1_16.txt AC 145 ms 12792 KB
1_17.txt AC 146 ms 12784 KB
1_18.txt AC 145 ms 12796 KB
1_19.txt AC 145 ms 12796 KB