제출 #484768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484768		dynam1c	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	289 ms	32072 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define all(x) x.begin(),x.end()

struct Fenwick {
        int n;
        vector<int> arr;
        Fenwick(int n) : n(n), arr(n+1) {}
        int query(int p) {
                int acc = 0;
                for (; p > 0; p -= p & -p)
                        acc += arr[p];
                return acc;
        }
        int query(int l, int r) {
                return query(r) - query(l);
        }
        void update(int i, int x) { 
                for (i++; i <= n; i += i & -i)
                        arr[i] += x;
        }
};

long long count_swaps(std::vector<int> s) {
        int n = s.size();
        map<int, set<int>> m;
        vector<bool> done(n);
        for (int i = 0; i < n; i++)
                m[s[i]].insert(i);
        Fenwick fen(n); 
        for (int i = 0; i < n; i++)
                fen.update(i, 1);
        ll res = 0;
        for (int i = 0; i < n; i++) {
                if (done[i]) continue;
                res += s[i] > 0;
                auto it = m[-s[i]].lower_bound(i);
                int j = *it;
                m[-s[i]].erase(it);
                done[i] = true;
                fen.update(i, -1);
                done[j] = true;
                fen.update(j, -1);
                res += fen.query(i, j);
        }
        return res;
}

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