| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 870733 | Eliorita | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "shoes.h:
#define int long long
#define pb push_back
#define x first
#define y second
#define getbit(u,i) ((u>>i)&1)
#define all(x) x.begin(),x.end()
#define N 200001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
int n,a[N],c[N],temp[N],nxt[N][2],pr[N],cnt;
int merge(int l,int mid,int r)
{
int cnt=0,i=l,j=mid,k=l;
while((i<=mid-1)&&(j<=r))
{
if(c[i]<=c[j]) temp[k++]=c[i++];
else
{
temp[k++]=c[j++];
cnt+=(mid-i);
}
}
while(i<=mid-1) temp[k++]=c[i++];
while(j<=r) temp[k++]=c[j++];
for(int i=l;i<=r;i++) c[i]=temp[i];
return cnt;
}
int mergesort(int l,int r)
{
int cnt=0;
if(l<r)
{
int mid=(l+r)/2;
cnt+=mergesort(l,mid);
cnt+=mergesort(mid+1,r);
cnt+=merge(l,mid+1,r);
}
return cnt;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=2*n;i++) cin>>a[i];
for(int i=2*n;i>=1;i--)
{
if(a[i]<0)
{
if(!nxt[-a[i]][1]) nxt[-a[i]][0]=i;
else
{
pr[i]=nxt[-a[i]][1];
nxt[-a[i]][1]=0;
}
}
else
{
if(!nxt[a[i]][0]) nxt[a[i]][1]=i;
else
{
pr[i]=nxt[a[i]][0];
nxt[a[i]][0]=0;
}
}
}
for(int i=1;i<=2*n;i++)
{
if(pr[i]!=0)
{
c[i]=++cnt;
c[pr[i]]=++cnt;
if(a[i]>0) swap(c[i],c[pr[i]]);
}
}
cout<<mergesort(1,2*n);
}