Submission #1141765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141765		Mike_Vu	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	17 ms	7240 KiB

shoes

#ifndef mikevui
//    #include "task.h"
#endif // mikevui

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
#define ALL(v) (v).begin(), (v).end()

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

struct BIT{
    int n;
    vector<int> bit;
    void init(int _n) {
        n = _n;
        bit.assign(n+1, 0);
    }
    void update(int k, int x) {
        while (k <= n) {
            bit[k] += x;
            k += k & (-k);
        }
    }
    int getsum(int k) {
        int res = 0;
        while (k > 0) {
            res += bit[k];
            k -= k & (-k);
        }
        return res;
    }
    int query(int l, int r) {
        if (l > r) return 0;
        return getsum(r)-getsum(l-1);
    }
};

const int maxn = 1e5+5;
int n, a[maxn];
vector<int> pos[maxn][2];
BIT bit;
ll ans;

ll count_swaps(vector<int> S) {
    n = S.size();
    for (int i = 1; i <= n; i++) {
        a[i] = S[i-1];
    }
    //queue val
    bit.init(n);
    ans = 0;
    for (int i = n; i; i--) {
        pos[abs(a[i])][a[i]>0].pb(i);
        bit.update(i, 1);
    }
    //iter + take val + pop val
    for (int i = 1; i <= n; i++) {
        int v = abs(a[i]), t = a[i]>0;
        if (pos[v][t].empty() || pos[v][t].back() != i) {
            continue;
        }
        ans += t;
        int cur = pos[v][t^1].back();
        pos[v][t^1].pop_back();
        pos[v][t].pop_back();
        ans += bit.query(i+1, cur-1);
        bit.update(i, -1);
        bit.update(cur, -1);
    }
    //plus ans, BIT
    return ans;
}

#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int N;
    vector<int> S;
    cin >> N;
    for (int i= 1; i <= N; i++) {
        int x;
        cin >> x;
        S.pb(x);
    }
    cout << count_swaps(S);
}
#endif // mikevui
/*
4
2 1 -1 -2

6
-2 2 2 -2 -2 2
*/

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