제출 #1155583

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

shoes

#include <bits/stdc++.h>
// #include "shoes.h"
// #define int long long
const int MAXN = 1e6 + 10;
const long long inf = 2e10;
const int MAXS = 1e5;
const int mod = 1e9 + 7;
const int zero = 0;
using namespace std;
int bit[MAXN];
map<int, queue<int>> q;
int s[MAXN];
void upd(int i, int sum){
    while(i < MAXN){
        bit[i] += sum;
        i += (i & (-i));
    }
}
long long find(int i){
    long long sum = 0;
    while(i > 0){
        sum += bit[i];
        i -= (i & (-i));
    }
    return sum;
}
long long count_swaps(vector<int> S){
    int n = S.size()/2;
    for(int i = 0; i < n*2; i++){
        s[i + 1] = S[i];
        upd(i + 1, 1);
    }
    long long ans = 0;
    for(int i = 1; i <= n*2; i++){
        q[s[i]].push(i);
    }
    for(int i = 1; i <= n*2; i++){
        if(s[i] < 0){
            if(find(i) - find(i - 1) == 0) continue;
            int y = q[-s[i]].front();
            q[s[i]].pop();
            q[-s[i]].pop();
            ans += find(y)- find(i + 1);
            upd(i, -1);
            upd(y, -1);
        }
        else{
            if(find(i) - find(i - 1) == 0) continue;
            int y = q[-s[i]].front();
            q[s[i]].pop();
            q[-s[i]].pop();
            ans += find(y) - find(i);
            upd(i, -1);
            upd(y, -1);
        }
    }
    return ans;
}
// int32_t main() {
//     // freopen("cowtip.in", "r", stdin);
//     // freopen("cowtip.out", "w", stdout);
//     ios_base::sync_with_stdio(false);cin.tie(0);
//     cout << count_swaps({-2, -1, 1, 2}) << '\n';
// }

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