제출 #144820

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144820		khrbuddy03	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	120 ms	16008 KiB

shoes

#include <bits/stdc++.h>
 
using namespace std;
 
using lint = long long;
 
const int maxn = 1e5 + 9;
 
struct fenwick {
    vector<lint> tree;
    fenwick(int _n) : tree(_n + 1, 0) {}
    lint get(int index) {
        lint sum = 0LL;
        while (0 < index) {
            sum += tree[index] * 1LL;
            index -= (index & -index);
        }
        return sum * 1LL;
    }
    void add(int index, lint value) {
        while (index < tree.size()) {
            tree[index] += value * 1LL;
            index += (index & -index);
        }
    }
};
 
lint count_swaps(vector<int> s) {
    int n = (int)s.size() / 2;
    vector<bool> check(n * 2, false);
    fenwick tree(n * 2);
    priority_queue<int> pq1[maxn], pq2[maxn];
    lint answer = 0LL;
    for (int i = 0; i < 2 * n; ++i) {
        if (s[i] > 0)
            pq1[s[i]].push(-i);
        else
            pq2[-s[i]].push(-i);
        tree.add(i + 1, 1LL);
    }
    for (int i = 0; i < 2 * n; ++i) {
        if (check[i])
            continue;
        int pos;
        if (s[i] > 0) {
            pos = -pq2[s[i]].top();
            pq2[s[i]].pop(); pq1[s[i]].pop();
            ++answer;
        } else {
            pos = -pq1[-s[i]].top();
            pq1[-s[i]].pop(); pq2[-s[i]].pop();
        }
        tree.add(i + 1, -1);
        tree.add(pos + 1, -1);
        answer += (tree.get(pos + 1) * 1LL - tree.get(i) * 1LL) * 1LL;
        check[i] = check[pos] = true;
    }
    return answer;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp: In member function 'void fenwick::add(int, lint)':
shoes.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (index < tree.size()) {
                ~~~~~~^~~~~~~~~~~~~

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