Submission #264194

#	Time	Username	Problem	Language	Result	Execution time	Memory
264194		hamerin	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	176 ms	8948 KiB

shoes

#include "shoes.h"

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using i64 = long long;
using d64 = long double;
using pi = pair<int, int>;
using pli = pair<i64, i64>;
using ti = tuple<int, int, int>;
using tli = tuple<i64, i64, i64>;

#define iterall(cont) cont.begin(), cont.end()
#define prec(n) setprecision(n) << fixed

const size_t fTsize = 1 << 18;
class fenwickTree {
   public:
    vector<int> vl;
    int N;

    fenwickTree() { vl.resize(fTsize); }

    int query(int t) {
        int ret = 0;
        while (t) ret += vl[t], t -= (t & -t);
        return ret;
    }

    int query(int l, int r) { return query(r) - query(l - 1); }

    void update(int t, int d = -1) {
        while (t < fTsize) vl[t] += d, t += (t & -t);
    }
};

i64 count_swaps(vector<int> s) {
    int N = s.size() >> 1;
    i64 ret = 0;

    set<pi> st;
    vector<pi> match;
    for (int i = 0; i < 2 * N; i++) {
        auto it = st.lower_bound({-s[i], 0});
        if (it != st.end() && it->first == -s[i]) {
            match.emplace_back(it->second, i);
            st.erase(it);
        } else {
            st.insert({s[i], i});
        }
    }
    sort(iterall(match));

    auto fT = fenwickTree();
    for (int i = 1; i <= 2 * N; i++) fT.update(i, 1);
    for (auto [l, r] : match) {
        ret += fT.query(++l, ++r);
        ret -= 2;

        if (s[l - 1] > s[r - 1]) ret += 1;

        fT.update(l);
        fT.update(r);
    }

    return ret;
}

Compilation message (stderr)

shoes.cpp: In member function 'void fenwickTree::update(int, int)':
shoes.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   37 |         while (t < fTsize) vl[t] += d, t += (t & -t);
      |                ~~^~~~~~~~

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