#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
#define int long long
#define pii pair<int,int>
int bit[maxn],n,cnt=0;
vector<pii> x;
int query(int a){
int res=0;
for(int i=a;i>=1;i-=(i&(-i))) res+=bit[i];
return res;
}
void update(int a){
for(int i=a;i<=n;i+=(i&(-i))) bit[i]++;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> n;
for(int i=1;i<=n;i++){
int a;cin >> a;
x.push_back({a,i});
}
sort(x.begin(),x.end());
int ans=0;
while(!x.empty()){
pii p=x.back();x.pop_back();
int sum=query(p.second);sum=min(sum,cnt-sum);
vector<int> add={p.second};
while(!x.empty() && x.back().first==p.first){
int a=query(x.back().second);
sum+=min(a,cnt-a);add.push_back(x.back().second);
x.pop_back();
}
//cout << cnt << ' ' << sum << '\n';
ans+=sum;cnt+=(int)add.size();
for(int v:add) update(v);
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
328 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
596 KB |
Output is correct |
6 |
Correct |
1 ms |
596 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
1 ms |
596 KB |
Output is correct |
9 |
Correct |
1 ms |
596 KB |
Output is correct |
10 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
2000 KB |
Output is correct |
2 |
Correct |
23 ms |
3880 KB |
Output is correct |
3 |
Correct |
30 ms |
5708 KB |
Output is correct |
4 |
Correct |
41 ms |
7344 KB |
Output is correct |
5 |
Correct |
26 ms |
7000 KB |
Output is correct |
6 |
Correct |
21 ms |
3760 KB |
Output is correct |
7 |
Correct |
49 ms |
9780 KB |
Output is correct |
8 |
Correct |
61 ms |
11256 KB |
Output is correct |
9 |
Correct |
62 ms |
13512 KB |
Output is correct |
10 |
Correct |
58 ms |
11452 KB |
Output is correct |