제출 #1198779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198779		andrejikus	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	183 ms	147632 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) { cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...); }
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)

const int N = 1e5 + 3;
queue<int> pz[N][2];

struct fenwick_tree {
    vector<int> bit;
    void init(int n) {
        bit.assign(n + 1, 0);
    }

    int sum(int i) {
        int s = 0;
        while (i > 0) {
            s += bit[i];
            i -= (i & (-i));
        }
        return s;
    }
    void add(int i, int val, int n) {
        while (i > 0 && i <= n) {
            bit[i] += val;
            i += (i & (-i));
        }
    }
    int get(int l, int r) {
        return sum(r) - (l > 0 ? sum(l-1) : 0);
    }
}; fenwick_tree fenwick;

long long count_swaps(vector<int> s) {
	int n = s.size();
	fenwick.init(n);
	set<pair<int, int>> st;
	for (int i = 0; i < n; i++) {
        int tp = (s[i] < 0 ? 0 : 1);
        pz[abs(s[i])][tp].push(i);
        st.insert({i, s[i]});
	}
	ll ans = 0;
	for (int i = 0; i < n; i += 2) {
        auto [j, sj] = *st.begin();
        st.erase(st.begin());
        int tp = (sj < 0 ? 0 : 1);
        pz[abs(sj)][tp].pop();
        int k = pz[abs(sj)][tp^1].front();
        pz[abs(sj)][tp^1].pop();
        st.erase(st.find(make_pair(k, -sj)));
        int add = fenwick.get(k, n);
        fenwick.add(k, 1, n);
        int raz = (k+add-i) - (tp == 0);
        ans += raz;
	}

	return ans;
}

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