#pragma GCC optimize("conserve-stack")
#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 int INF = 1e9;
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 ptr1 = 0, ptr2 = 0;
static vector<int> vec;
vec = {A};
rep (i, 0, 20) {
if ((1 << i) > SZ(lc) - ptr1) break;
rep (j, 1, (1 << i)) vec.push_back(lc[ptr1++]);
rep (j, 1, (1 << i)) {
if (ptr2 < SZ(rc)) vec.push_back(rc[ptr2++]);
}
}
while (ptr1 < SZ(lc)) vec.push_back(lc[ptr1++]);
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) {
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];
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 > n) return vector<int> (0);
if (id * 2 > n) {
return vector<int> (1, val);
}
if (id * 2 + 1 > n) {
return {min(val, a[id * 2]), max(val, a[id * 2])};
}
if (dp[id].find(val) != dp[id].end())
return dp[id][val];
Assign (id, val);
return dp[id][val];
}
void solution () {
// cin >> n;
// rep (i, 1, n) cin >> a[i];
n = 1e5;
rep (i ,1, n) a[i] = i;
random_shuffle(a + 1, a + 1 + n);
vector<int> res;
Assign (1, a[1]);
// 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 |
55 ms |
35816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
35816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
35816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
35816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
35816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
