Submission #1369817

#TimeUsernameProblemLanguageResultExecution timeMemory
1369817altayeb_132Arranging Shoes (IOI19_shoes)C++20
100 / 100
144 ms14204 KiB
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
struct segtree {
    vector<int> sm;
    int sz = 1;
    segtree(int n) {
        while (sz < n)
            sz *= 2;
        sm.assign(sz * 2, 0);
    }
    void set(int l, int r, int lx, int rx, int x) {
        if (l <= lx && rx <= r) {
            sm[x] += 1;
            return;
        }
        if (l >= rx || lx >= r)
            return;
        int m = (lx + rx) / 2;
        set(l, r, lx, m, x * 2);
        set(l, r, m, rx, x * 2 + 1);
    }
    void set(int l, int r) {
        if (l >= r) return;
        set(l, r, 0, sz, 1);
    }
    int get(int idx) {
        idx += sz;
        int cnt = 0;
        while (idx > 0) {
            cnt += sm[idx];
            idx /= 2;
        }
        return cnt;
    }
};
long long count_swaps(vector<int> s) {
    int n = s.size();
    ll ans = 0;
    int vis[n + 10] = {};
    segtree st(n);
    set<array<int, 2>> nm;
    for (int i = 0; i < n; i++)
        nm.insert({s[i], i});
    for (int i = 0; i < n; i++) {
        if (vis[i])
            continue;
        nm.erase({s[i], i});
        auto nxt = nm.lower_bound({-s[i], 0});
        int idx = (*nxt)[1];
        vis[i] = vis[idx] = 1;
        nm.erase(nxt);
        int i1 = i + st.get(i);
        int idx1 = idx + st.get(idx);
        ans += idx1 - i1 - 1;
        if (s[i] > 0)
            ans++;
        st.set(i, idx);
    }
    return ans;
}


#include "shoes.h"
// int main() {int n;assert(1 == scanf("%d", &n));vector<int> S(2 * n);for (int i = 0; i < 2 * n; i++)assert(1 == scanf("%d", &S[i]));fclose(stdin);long long result = count_swaps(S);printf("%lld\n", result);fclose(stdout);return 0;}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...