| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1265032 | hitsuuj | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
//CEK ENDL DAN INT LL
#define endl '\n'
#define inf 1e18
#define ti tuple<int,int,int>
#define meekucaon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod=1e9+7;
int sf(int a){return (a%mod+mod)%mod;}
int kal(int a,int b){return (sf(a)*sf(b))%mod;}
int tam(int a,int b){return (sf(a)+sf(b))%mod;}
int kur(int a,int b){return (sf(a)+mod-sf(b))%mod;}
int inv(int a){
if(a<=1) return 1;
return mod-(int)(mod/a)*inv(mod%a)%mod;
}
int bag(int a,int b){return kal(sf(a),inv(b));}
const long long lim=3e5;
long long n;
long long tri[lim+10];
long long seek(long long x){
long long res=0;
while(x<=n){
res+=tri[x];
x+=x&-x;
}
return res;
}
void upd(long long x){
while(x>0){
tri[x]++;
x-=x&-x;
}
}
signed main(){
meekucaon
cin>>n;
vector<int>s(n);
for(auto &x:s)cin>>x;
map<long long,queue<long long>>q;
vector<long long>tan(n);
long long cnt=1;
for(long long i=0;i<n;i++) q[s[i]].push(i);
for(long long i=0;i<n;i++){
if(tan[i])continue;
long long pas=q[-s[i]].front();
q[-s[i]].pop();
q[s[i]].pop();
if(s[i]<0) tan[i]=cnt;
else tan[pas]=cnt;
cnt++;
if(s[i]>0) tan[i]=cnt;
else tan[pas]=cnt;
cnt++;
}
long long ans=0;
for(long long i=0;i<n;i++){
// cout<<tan[i]<<" ";
ans+=seek(tan[i]);
upd(tan[i]);
}
// cout<<endl;
for(int i=0;i<=lim;i++)tri[i]=0;
cout<<ans;
}