| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 849984 | tosivanmak | Arranging Shoes (IOI19_shoes) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct pairs{
ll l,r;
bool operator<(const pairs& p)const{
// l,r,p.l,p.r
ll cnt=0;
if(r<l){
cnt++;
}
if(p.l<l){
cnt++;
}
if(p.l<r){
cnt++;
}
if(p.r<l){
cnt++;
}
if(p.r<r){
cnt++;
}
if(p.r<p.l){
cnt++;
}
ll cnt2=0;
// p.l,p.r,l,r
if(p.r<p.l){
cnt2++;
}
if(l<p.l){
cnt2++;
}
if(l<p.r){
cnt2++;
}
if(r<p.l){
cnt2++;
}
if(r<p.r){
cnt2++;
}
if(r<l){
cnt2++;
}
// cout<<1;
return cnt<=cnt2;
}
};
vector<pairs>bruh;
void merge(ll l, ll r){
ll mid=(l+r)>>1;
ll ptr=l,ptr2=mid+1;
vector<pairs>get;
for(int i=l;i<=r;i++){
if(ptr==mid+1){
get.push_back(bruh[ptr2]);
ptr2++;
}
else if(ptr2==r+1){
get.push_back(bruh[ptr]);
ptr++;
}
else if(bruh[ptr]<bruh[ptr2]){
get.push_back(bruh[ptr]);
ptr++;
}
else{
get.push_back(bruh[ptr2]);
ptr2++;
}
}
for(int i=l;i<=r;i++){
bruh[i]=get[i-l];
}
}
void merge_sort(ll l, ll r){
if(l==r){
return;
}
ll mid=(l+r)>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
merge(l,r);
}
struct FEN{
vector<ll>fen;
void init(ll n){
fen.resize(n+5);
for(int i=0;i<=n+4;i++){
fen[i]=0;
}
}
void upd(ll n, ll m, ll val){
for(int i=n;i<=m;i+=i&(-i)){
fen[i]+=val;
// cout<<i;
}
}
ll sum(ll e){
ll su=0;
while(e>=1){
su+=fen[e];
e-=e&(-e);
}
// cout<<1;
return su;
}
}f;
vector<int>adj[1000005],adj2[1000005]; int ptr[1000005];
long long count_swaps(std::vector<int> s) {
vector<ll>make;
ll why=s.size();
for(int i=0;i<why;i++){
if(s[i]<0){
make.push_back(-(s[i]));
adj[-(s[i])].push_back(i+1);
}
else{
adj2[s[i]].push_back(i+1);
}
}
for(int i=0;i<=why+4;i++){
ptr[i]=0;
}
// for(auto u: adj[2]){
// cout<<u<<" ";
// }
ll siz=make.size();
for(int i=0;i<siz;i++){
bruh.push_back({adj[make[i]][ptr[make[i]]],adj2[make[i]][ptr[make[i]]]});
ptr[make[i]]++;
}
// sort(bruh.begin(),bruh.end());
// for(int i=0;i<bruh.size();i++){
// for(int j=0;j<bruh.size()-1;j++){
// if(bruh[j+1]<bruh[j]){
// swap(bruh[j],bruh[j+1]);
// }
// }
// }
merge_sort(0,bruh.size()-1);
vector<ll>real;
ll siz2=bruh.size();
for(int i=0;i<siz2;i++){
real.push_back(bruh[i].l);
real.push_back(bruh[i].r);
}
// for(auto u: real){
// cout<<u<<" ";
// }
f.init(300000);
ll ans=0;
ll siz3=real.size();
for(int i=0;i<siz3;i++){
ans+=f.sum(300000)-f.sum(real[i]);
// cout<<f.sum(200000)<<" "<<real[i]<<" ";
// cout<<f.sum(real[i])<<"\n";
f.upd(real[i],300000,1);
}
return ans;
// return 0;
}
// #ifndef ONLINE_JUDGE
int main() {
int n;
cin>>n;
vector<int> S(2 * n);
for (int i = 0; i < 2 * n; i++){
cin>>S[i];
}
long long result = count_swaps(S);
cout<<result<<"\n";
return 0;
}
// #endif