?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
193683141 |
Practice: hydra_cody |
1579E2 - 40 | C++17 (GCC 7-32) | Accepted | 280 ms | 12720 KB | 2023-02-15 09:47:35 | 2023-02-15 09:47:35 |
#include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define endl "\n" #define pb push_back #define pf push_front #define pob pop_back #define pof pop_front #define mp make_pair #define fi first #define se second #define set_bits __builtin_popcountll #define precise(ans) cout<<fixed<<setprecision(15)<<ans #define fo(i,n) for(ll i=0;i<n;i++) #define Fo(i,k,n) for(ll i=k;k<n?i<n:i>n;k<n?i+=1:i-=1) #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++) #define sz(x) ((ll)(x).size()) #define all(x) x.begin(), x.end() #define PI 3.1415926535897932384626 #define MOD 1000000007 #define MOD1 998244353 typedef long long ll; typedef unsigned long long ull; typedef long double lld; typedef pair<ll, ll> pii; typedef pair<ll, ll> pl; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<pii> vpii; typedef vector<pl> vpl; template <typename T> using prq_mx = priority_queue<T>; template <typename T> using prq_mn = priority_queue<T, vector<T>, greater<T>>; const double eps = 1e-9; const ll INF = (ll) 1e9; const ll inf64 = 2e18; const ll INF64 = 9e18; #ifndef ONLINE_JUDGE #define debug(x) cerr << #x <<" "; _prll(x); cerr << endl; #else #define debug(x) #endif void _prll(ll t) {cerr << t;} void _print(ll t) {cerr << t;} void _prll(string t) {cerr << t;} void _prll(char t) {cerr << t;} void _prll(lld t) {cerr << t;} void _prll(double t) {cerr << t;} void _prll(ull t) {cerr << t;} template <class T, class V> void _prll(pair <T, V> p); template <class T> void _prll(vector <T> v); template <class T> void _prll(set <T> v); template <class T, class V> void _prll(map <T, V> v); template <class T> void _prll(multiset <T> v); template <class T, class V> void _prll(pair <T, V> p) {cerr << "{"; _prll(p.fi); cerr << ","; _prll(p.se); cerr << "}";} template <class T> void _prll(vector <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T> void _prll(set <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T> void _prll(multiset <T> v) {cerr << "[ "; for (T i : v) {_prll(i); cerr << " ";} cerr << "]";} template <class T, class V> void _prll(map <T, V> v) {cerr << "[ "; for (auto i : v) {_prll(i); cerr << " ";} cerr << "]";} //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ll n; vector<ll> bit; void update(ll k,ll val) { while(k<=n) { bit[k]+=val; k+=(k&(-k)); } } ll sum(ll k) { ll res=0; while(k>0) { res+=bit[k]; k-=(k&(-k)); } return res; } ll query(ll l,ll r) { return sum(r)-sum(l-1); } void chal() { ll m; cin>>m; vl aa(m),cc(m); map<ll,ll> bb; n=1; fo(i,m){ cin>>aa[i]; cc[i]=aa[i]; } sort(all(cc)); fo(i,m){ if(bb[cc[i]]==0){ bb[cc[i]]=n; n++; } } debug(bb) bit.clear(); bit.resize(n+1,0); // debug(bit); ll ans=0; fo(i,m){ ll x=sum(bb[aa[i]]-1); ll y=i-sum(bb[aa[i]]); // cout<<aa[i]<<" "<<x<<" "<<y<<endl; ans+=min(x,y); update(bb[aa[i]],1); // debug(bit); } cout<<ans<<endl; } //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ int32_t main() {ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); srand(chrono::high_resolution_clock::now().time_since_epoch().count()); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("Error.txt", "w", stderr); #endif ll t; t = 1; cin >> t; for (ll i = 1; i <= t; i++) {chal();} return 0;}
?
?
?
?