제출 #1276082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276082		nanaseyuzuki	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	223 ms	75560 KiB

shoes

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 1e6 + 5, bm = (1 << 20) + 1;
const int inf = 1e9;

int n, a[mn];
map <int, queue<int>> mp;

int bit[mn];

void add(int u, int val){
    while(u <= n){
        bit[u] += val;
        u += (u & -u);
    }
}

int get(int u){
    int res = 0;
    while(u){
        res += bit[u];
        u -= (u & -u);
    }
    return res;
}

ll count_swaps(vector <int> s){
    n = s.size();
    for(int i = 0; i < n; i++){
        a[i + 1] = s[i];
    }
    ll res = 0;
    for(int i = 1; i <= n; i++){
        if(mp.count(- a[i]) && mp[- a[i]].size()){
            int j = mp[- a[i]].front(); mp[- a[i]].pop();
            if(a[i] < 0){
                add(i, 1);
                res += 1ll * (i - get(i));
                add(j, 1);
                res += 1ll * (j - get(j));
            }
            else{
                add(j, 1);
                res += 1ll * (j - get(j));
                add(i, 1);
                res += 1ll * (i - get(i));
            }
        }
        else{
            mp[a[i]].push(i);
        }
    }
    return res;
}

// signed main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     cout.tie(NULL);
//     cout << count_swaps({2, 1, -1, -2}) << '\n';
// }

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