| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1238600 | em4ma2 | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define pb push_back
#define ll long long
const ll inf=1e9+4;
const ll off=(1<<19);
ll tr[off*2];
ll op(ll trl,ll trr){
return trl+trr;
}
void upd(int i,ll v){
i+=off;
tr[i]=v;
while (i/=2){
int xl=i*2,xr=xl+1;
tr[i]=op(tr[xl],tr[xr]);
}
}
ll query(int ql,int qr,int l=0,int r=off-1,int x=1){
if (ql<=l && r<=qr)return tr[x];
if (l>qr || r<ql)return 0;
int mid=(l+r)/2;
int xl=x*2,xr=xl+1;
int trl=query(ql,qr,l,mid,xl),trr=query(ql,qr,mid+1,r,xr);
return op(trl,trr);
}
ll count_swaps(vector<int>a){
int n=a.size();
int us[n+1];
for (int i=0;i<n;i++){
upd(i,1);
us[i]=1;
}
vector<int>adp[n+1];
vector<int>adn[n+1];
vector<int>p(n+1);
//cout<<"DSFI";
for (int i=0;i<n;i++){
if (a[i]>0){
if (adn[abs(a[i])].size()){
p[i]=(adn[abs(a[i])].back());
p[adn[abs(a[i])].back()]=(i);
adn[abs(a[i])].pop_back();
}else{
adp[a[i]].pb(i);
}
}
else{
//cout<<'d';
if (adp[abs(a[i])].size()){
p[i]=(adp[abs(a[i])].back());
p[adp[abs(a[i])].back()]=(i);
adp[abs(a[i])].pop_back();
}else{
//cout<<i<<endl;
adn[abs(a[i])].pb(i);
}
}
}
// for (int i=0;i<n;i++){
// cout<<p[i]<<" ";
// }cout<<endl;
ll sum=0;
for (int i=n-1;i>=0;i--){
if (!us[i])continue;
// for (auto x:us){
// cout<<x<<" ";
// }cout<<endl;
int r=i-1,l=p[i]+1;
//cout<<l<<" "<<r<<endl;
if (l<r){
ll x=query(l,r);
sum+=x;
//cout<<x<<endl;
}
upd(i,0);
upd(p[i],0);
us[i]=0,us[p[i]]=0;
if (a[i]<0 && a[p[i]]>0)sum++;
//cout<<sum<<" ";
}
return sum;
}
int main() {
int n;
assert(1 == scanf("%d", &n));
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++)
assert(1 == scanf("%d", &S[i]));
fclose(stdin);
long long result = count_swaps(S);
printf("%lld\n", result);
fclose(stdout);
return 0;
}