-
Notifications
You must be signed in to change notification settings - Fork 1
/
1162.cpp
98 lines (98 loc) · 1.57 KB
/
1162.cpp
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
const int maxn = 2e5+5;
int n;
int v[maxn];
int b[maxn];
int o[maxn];
void update(int x) {
while (x <= n) {
b[x]++;
x += x & (-x);
}
}
int query(int x) {
int ret = 0;
while (x) {
ret += b[x];
x -= x & (-x);
}
return ret;
}
void s1() {
ll ans = 0;
f1 (n) {
ans += i - 1 - query(v[i]);
update(v[i]);
}
cout << ans << ' ';
}
void s2 () {
int ans = 0;
f1(n) {
while(v[i] != i) {
ans++;
swap(v[i],v[v[i]]);
}
}
f1(n) {
v[i] = o[i];
}
cout << ans << ' ';
}
void s3 () {
vector<int>LIS{v[1]};
fr(i,2,n+1) {
if (v[i] > LIS.back()) {
LIS.pb(v[i]);
}
else {
*lower_bound(all(LIS),v[i]) = v[i];
}
}
cout << n - LIS.size() << ' ';
}
void s4 () {
int ans = n;
for (int i = n ; i >= 1 ; i--) {
if (v[i] == ans) {
ans--;
}
}
cout << ans << '\n';
}
void solve() {
cin >> n;
f1(n) {
cin >> v[i];
o[i] = v[i];
}
s1();
s2();
s3();
s4();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int c = 0;
int t;
if (!c) {
t = 1;
}
else {
cin >> t;
}
while (t--) {
solve();
}
}