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