제출 #1334701

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

shoes

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
int FST[2*maxn] ={0};
int n, q, a, b;
void modify(int p, int value){
    for(FST[p+=n]+=value; p > 1; p>>=1){
        FST[p>>1]=FST[p]+FST[p^1];
    }
}
int query(int l, int r){
    int res = 0;
    for(l+=n, r+=n;l<r;l>>=1,r>>=1){
        if (l&1) res += FST[l++];
        if (r&1) res += FST[--r];
    }
    return res;
}
long long count_swaps(vector<int>S){
    n = S.size();
    int D = 0, i = 0, r = 0;
    while (D < S.size()/2){
        while (S[i] >= 0){
            i++;
        }
        r += i - D*2 + query(i+1, S.size());
        modify(i, 1);
        int j = 0;
        while (S[j] != -S[i]){
            j++;
        }
        S[i] = 0;
        S[j] = 0;
        r += j - D*2 - 1 + query(j+1, S.size());
        modify(j, 1);
        D++;
        i++;
    }
    return r;
}

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