Submission #379509

#	Time	Username	Problem	Language	Result	Execution time	Memory
379509		N_o_o_B	무제 (POI11_rot)	C++14	36 / 100	1091 ms	24240 KiB

Main

#include <bits/stdc++.h>

namespace std
{

template <class Fun>
class y_combinator_result
{
    Fun fun_;

public:
    template <class T>
    explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

    template <class... Args>
    decltype(auto) operator()(Args &&... args)
    {
        return fun_(std::ref(*this), std::forward<Args>(args)...);
    }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun)
{
    return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second

clock_t time_p = clock();
void time_taken()
{
    time_p = clock() - time_p;
    cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}

const ll mod = 1e9 + 7;
const ll INF = 1e18;

#include <bits/extc++.h>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// s.order_of_key(x) -> Number of elements in s strictly smaller than x
// auto it = s.find_by_order(k) -> iterator to the kth smallest element(0-indexed)

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int n;
    cin >> n;

    ll ans = 0;
    std::y_combinator([&](auto self) -> oset<int> {
        int p;
        cin >> p;
        oset<int> ret;
        if (p)
        {
            ret.insert(p);
            return ret;
        }
        ret = self();
        oset<int> foo = self();
        if (sz(ret) < sz(foo))
        {
            ll i1 = 0, i2 = 0;
            for (auto& x : ret)
            {
                int lt = (int)foo.order_of_key(x);
                int gt = sz(foo) - lt;
                i1 += lt;
                i2 += gt;
            }
            ans += min(i1, i2);
            for (auto pp : ret)
            {
                foo.insert(pp);
            }
            return foo;
        }
        else
        {
            ll i1 = 0, i2 = 0;
            for (auto x : foo)
            {
                int lt = (int)ret.order_of_key(x);
                int gt = sz(ret) - lt;
                i1 += gt;
                i2 += lt;
            }
            ans += min(i1, i2);
            for (auto pp : foo)
            {
                ret.insert(pp);
            }
            return ret;
        }
    })();

    cout << ans << endl;

    time_taken();
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10