| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 854642 | AliHasanli | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<vector>
#include<map>
#include<set>
using namespace std;
vector<int>sgtree(262144);
map<int,set<int>>mp;
int indd(int ind)
{
int ans=131072+ind;
return ans;
}
void update(int ind)
{
if(ind==1){sgtree[ind]+=1;return;}
sgtree[ind]+=1;
update(ind/2);
}
int query(int L,int R,int l,int r,int index)
{
if(l>r) return 0;
if(r<L || R<l)return 0;
if(l==r)return sgtree[index];
if(L<=l && r<=R) return sgtree[index];
return query(L,R,l,(l+r)/2,index*2)+query(L,R,(r+l)/2+1,r,index*2+1);
}
long long count_swaps(vector<int> s)
{
long long ans=0;
int a[s.size()]={0};
for(int i=0;i<s.size();i++)
sgtree[131072+i]=a[i];
for(int i=0;i<s.size();i++)
mp[s[i]].insert(i);
for(int i=0;i<s.size();i++)
{
if(a[i]==0)
{
a[i]=1;
mp[s[i]].erase(0);
mp[-s[i]].erase(0);
int nextind=0;
update(indd(i));
for(int j:mp[-s[i]])
{
nextind=j;
break;
}
update(indd(nextind));
a[nextind]=1;
if(i+1==nextind)
if(s[i]>s[nextind])ans++;
if(i+1<nextind)
{
ans+=(nextind-i-1-query(i+2,nextind,1,131072,1));
if(s[i]>s[nextind])ans++;
}
}
}
return ans;
}
//1 2 3 4 -1 -2 -3 -4
//1 1 1 1 1 1 1 1
int main()
{
int n;
cin>>n;
vector<int>s(2*n);
for(int i=0;i<2*n;i++)
cin>>s[i];
cout<<count_swaps(s);
return 0;
}// 1 -1 -1 1
// 1: 1 4
//-1: 2 3