#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 2e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const ll INF = 1e17;
const int BASE = 137;
int n;
int a[N];
map<int, vector<int>> dp[N];
vector<int> Merge (int A, vector<int> lc, vector<int> rc) {
int pos = 0;
vector<int> vec = {A};
assert (SZ(lc) >= SZ(rc));
while (pos < SZ(rc)) {
vec.push_back(lc[pos]);
vec.push_back(rc[pos]);
++pos;
}
while (pos < SZ(lc)) vec.push_back(lc[pos++]);
return vec;
}
bool compare (vector<int> v1, vector<int> v2) {
int pos = 0;
assert (SZ(v1) == SZ(v2));
while (v1[pos] == v2[pos]) ++pos;
return v1[pos] < v2[pos];
}
vector<int> calc (int id, int val);
void Assign (int root, int valr) {
if (root * 2 > n) {
dp[root][valr] = {valr};
return;
}
if (root * 2 + 1 > n) {
dp[root][valr] = {min(valr, a[root * 2]), max(valr, a[root * 2])};
return;
}
int lc = root * 2, rc = root * 2 + 1;
if (valr < a[lc] && valr < a[rc]) {
vector<int> t1 = calc (lc, a[lc]), t2 = calc (rc, a[rc]);
dp[root][valr] = Merge (valr, t1, t2);
}
else if (a[lc] < min(valr, a[rc])) {
vector<int> t1 = calc (lc, valr), t2 = calc (rc, a[rc]);
dp[root][valr] = Merge (a[lc], t1, t2);
}
else {
int B = min (valr, a[lc]);
int C = max (valr, a[lc]);
int A = a[rc];
// cout << root <<" "<<A <<"hihi:\n";
vector<int> t1 = Merge (A, calc (lc, B), calc (rc, C)), t2 = Merge (A, calc (lc, C), calc (rc, B));
if (compare (t1, t2)) dp[root][valr] = t1;
else dp[root][valr] = t2;
}
}
vector<int> calc (int id, int val) {
if (id * 2 > n) {
// cout << id <<"hihihi\n";
return dp[id][val] = vector<int> (1, val);
}
if (id * 2 + 1 > n) {
return dp[id][val] = {min(val, a[id * 2]), max(val, a[id * 2])};
}
if (dp[id].find(val) != dp[id].end())
return dp[id][val];
// cout << id<<" "<<val<<"hihi\n";
Assign (id, val);
return dp[id][val];
}
void solution () {
cin >> n;
rep (i, 1, n) cin >> a[i];
vector<int> res;
Assign (1, a[1]);
// cout <<"\n";
iter (&id, dp[1][a[1]]) cout << id <<" ";
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// file ("c");
int num_Test = 1;
// cin >> num_Test;
while (num_Test--)
solution();
}
/*
5 10
1 2
3 1
4 2
5 3
1 4
2 3
3 5
4 5
3 4
1 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
