제출 #1288765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288765		ghammazhassan	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1 ms	352 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--;
        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;
}
// signed main() {
// 	#ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
//     #endif
//     cin >> 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);

// 	ll result = count_swaps(S);

// 	printf("%lld\n", result);
// 	fclose(stdout);
// 	return 0;
// }

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