Submission #686706

#	Time	Username	Problem	Language	Result	Execution time	Memory
686706		Bliznetc	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	625 ms	150748 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second

typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vi >  vvi;

int t[800400];

void upd (int v, int l, int r, int pos) {
    if (l > pos || r < pos){
        return;
    }
    if (l  == r) {
        t[v] = 1;
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * v, l, mid, pos);
    upd(2 * v + 1, mid + 1, r, pos);
    t[v] = t[2 * v] + t[2 * v + 1];
}

int get_sum (int v, int l, int r, int tl, int tr) {
    if (l > tr || r < tl) {
        return 0;
    }
    if (l >= tl && r <= tr) {
        return t[v];
    }
    int mid = (l + r) / 2;
    return get_sum(2 * v, l, mid, tl, tr) + get_sum(2 * v + 1, mid + 1, r, tl, tr);
}


long long count_swaps(vector<int> b) {
    int n = b.sz;
    int a[n + 7];
    int used[n + 7];
    for (int i = 0; i < n; i++) {
        a[i + 1] = b[i];
        used[i + 1] = 0;
    }

    map <int, deque<int> > m;
    for (int i = 1; i <= n; i++) {
        m[a[i]].pb(i);
    }

    long long cnt = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        if (used[i]) {
            continue;
        }
        if (a[i] > 0) {
            int pos = m[-a[i]].front();
            cnt = get_sum (1, 1, n, i, pos);
            ans += pos - i - cnt;
            used[pos] = 1;
            upd(1, 1, n, pos);
            m[a[i]].pop_front();
            m[-a[i]].pop_front();
        }
        else {
            int pos = m[-a[i]].front();
            cnt = get_sum (1, 1, n, i, pos);
            ans += pos - i - 1 - cnt;
            used[pos] = 1;
            upd(1, 1, n, pos);
            m[a[i]].pop_front();
            m[-a[i]].pop_front();
        }
//        cout << i << " " << ans << "\n";
    }
    return ans;
}
/*
signed main() {
    vi a;
    a.pb(-2);
    a.pb(2);
    a.pb(2);
    a.pb(-2);
    a.pb(-2);
    a.pb(2);
    cout << count_swaps(a);
}
 */

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