Submission #318621

#	Time	Username	Problem	Language	Result	Execution time	Memory
318621		penguin71630	Arranging Shoes (IOI19_shoes)	C++14	25 / 100	182 ms	140264 KiB

shoes

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

#define flag(_a) cout << "Still alive at flag " << _a << '\n';
#define dbg(_a, _b) cout << "var " << _a << " -> " << _b << '\n';
#define dbg_itv(_l, _r, _val) cout << "itv (" << _l << ", " << _r << ") -> " << _val << '\n';
using namespace std;

typedef long long ll;
const int maxn = 2e5 + 1;

int n;
ll bit[maxn];
vector<queue<int> > L, R;

int lb(int x) {return x & (-x);}

void build() {
    for (int i = 1; i <= n; i++) {
        bit[i] = (i - (i-lb(i)+1) + 1);
    }
}

void modify(int x) {
    for (; x <= n; x += lb(x)) {
        bit[x]--;
    }
}

ll qry(int x) {
    ll sum = 0;
    for (; x > 0; x -= lb(x)) {
        sum += bit[x];
    }
    return sum;
}

ll count_swaps(vector<int> s) {
    n = (int)s.size();
    L.resize(n/2+1);
    R.resize(n/2+1);
	for (int i = 0; i < n; i++) {
	    if (s[i] < 0) L[abs(s[i])].push(i+1);
	    else R[abs(s[i])].push(i+1);
	}
    build();

	ll ans = 0;
	for (auto & i : s) {
        int j = abs(i);
        if (L[j].empty()) continue;
        int l = L[j].front(); L[j].pop();
        int r = R[j].front(); R[j].pop();
        if (r < l) {
            ans++;
            swap(l, r);
            assert(i > 0);
        }
        ll chg = 0;
        if (r-l > 1) chg = qry(r-1) - qry(l);
        ans += chg;
//        dbg_itv(l, r, chg);
        modify(l); modify(r);
	}

	return ans;
}
/*
2
2 1 -1 -2
 */

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