제출 #1280472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280472		cnastea	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	103 ms	23932 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int d[600000], m = 1;

void add(int l, int r){
    l += m; r += m;
    while(l < r){
        if(l%2) d[l++ - 1]++; l /= 2;
        if(r%2) d[--r - 1]++; r /= 2;
    }
}

int sum(int x){
    int s = 0; x += m;
    while(x){
        s += d[x-1]; x /= 2;
    }
    return s;
}

long long count_swaps(vector<int> a){
    long long n = a.size(), r = 0, b[n]; set<int> p[n/2+1], q[n/2+1];
    while(m < n) m *= 2;
    for(int i = 0; i < n; i++){
        if(a[i] < 0) p[-a[i]].insert(i); else q[a[i]].insert(i); b[i] = 0;
    }
    for(int i = 0; i < n; i++){
        if(b[i]) continue; b[i] = 1;
        if(a[i] > 0){
            q[a[i]].erase(q[a[i]].begin());
            int w = *p[a[i]].begin(); p[a[i]].erase(p[a[i]].begin());
            r += w+sum(w)-sum(i)-i; add(i, w); b[w] = 1;
        }
        else{
            p[-a[i]].erase(p[-a[i]].begin());
            int w = *q[-a[i]].begin(); q[-a[i]].erase(q[-a[i]].begin());
            r += w+sum(w)-sum(i)-i-1; add(i, w); b[w] = 1;
        }
    }
    return r;
}

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