-
Notifications
You must be signed in to change notification settings - Fork 11
/
Permutation Graph
83 lines (79 loc) · 2.45 KB
/
Permutation Graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cassert>
#include <set>
using namespace std;
int sq(int x) { return x * x; }
int main() {
int t;
cin >> t;
for (int tc = 0; tc < t; ++tc) {
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n+1);
for (auto& x : a) cin >> x;
for (int i = 0; i < n; ++i) {
b[a[i]] = i;
}
vector<pair<int,int>> mins, maxs;
mins.emplace_back(a[0], 0);
maxs.emplace_back(a[0], 0);
int d = 1e9;
for (int i = 1; i < n; ++i) {
int p = a[i-1];
int t = 0;
if (a[i] > p) {
while (maxs.size() > 0 && a[i] > maxs.back().first) {
maxs.pop_back();
}
// cerr << "last_max: " << maxs.back().first << endl;
if (maxs.empty()) {
t = 0;
maxs.emplace_back(a[0], 0);
} else {
t = b[maxs.back().first];
}
auto min_min = mins.back();
while (!mins.empty() && b[mins.back().first] >= t) {
// std::cerr << "remove min: " << mins.back().first << " t: " << t << endl;
if (mins.back().first < min_min.first) {
min_min = mins.back();
}
mins.pop_back();
}
// std::cerr << "back min: " << min_min.first << endl;
mins.push_back(min_min);
maxs.emplace_back(a[i], mins.back().second + 1);
//cerr << "new max: " << a[i] << " prev min: " << mins.back().first << " d: " << mins.back().second + 1 << endl;
} else {
while (mins.size() > 0 && a[i] < mins.back().first) {
mins.pop_back();
}
if (mins.empty()) {
t = 0;
mins.emplace_back(a[0], 0);
} else {
t = b[mins.back().first];
}
auto max_max = maxs.back();
while (!maxs.empty() && b[maxs.back().first] >= t) {
//std::cerr << "remove max: " << maxs.back().first << " t: " << t << endl;
if (maxs.back().first > max_max.first) {
max_max = maxs.back();
}
maxs.pop_back();
}
// std::cerr << "back max: " << max_max.first << endl;
maxs.push_back(max_max);
// cerr << "new min: " << a[i] << " prev max: " << maxs.back().first << " d: " << maxs.back().second + 1 << endl;
mins.emplace_back(a[i], maxs.back().second + 1);
}
}
d = a.back() == maxs.back().first ? maxs.back().second : mins.back().second;
cout << d << '\n';
}
}