제출 #1288823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288823		ghammazhassan	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1 ms	344 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define fi first
#define se second
const int N=1e5+5;
int n , m , c , w , k , t=1 , q=1 , x , y , z , l , r;
int fn[N];
void add(int i,int x){
    if (i<N){
        fn[i]+=x;
        add(i+(i&-i),x);
    }
}
int pr(int i){
    if (i==0)return 0;
    return fn[i]+pr(i-(i&-i));
}
ll count_swaps(vector<int>a)
{   
    int n=a.size()/2;
    a.push_back(a[2*n-1]);
    for (int i=2*n-1;i>0;i--){
    	a[i]=a[i-1];
    }
    map<int,queue<int>>d;
    for (int i=1;i<=2*n;i++){
        d[a[i]].push(i);
    }
    ll c=0;
    vector<pair<int,int>>k;
    for (int i=1;i<=2*n;i++){
        if (d[a[i]].size() and d[a[i]].front()==i){
            k.push_back({d[-a[i]].front()-i,i});
            d[a[i]].pop();
            d[-a[i]].pop();
        }
    }
    sort(k.begin(),k.end());
    for (int i=0;i<n;i++){
        c+=k[i].fi;
        if (a[k[i].se]<0)c--;
        for (int j=0;j<i;j++){
            if (k[j].se>k[i].se and k[j].se+k[j].fi<k[i].fi+k[i].se){
                c--;
            }
        }
        // c-=pr(k[i].fi+k[i].se)-pr(k[i].se);
        // add(k[i].se,1);
        // add(k[i].se+k[i].fi,-1);
    }
    return c;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15