제출 #318782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318782		penguin71630	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	190 ms	139108 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 + 2;

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

ll lb(ll x) {return x & (-x);}
void build() {
    for (int i = 1; i <= n; i++) bit[i] = lb(i);
}
void modify(ll x) {
    for (; x <= n; x += lb(x)) bit[x]--;
}
ll qry(ll 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[-s[i]].push(i+1);
	    else R[s[i]].push(i+1);
	}
	build();

	ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (qry(i+1)) {
            int j = abs(s[i]);
            if (L[j].empty() || R[j].empty()) continue;
            int l = L[j].front(); L[j].pop();
            int r = R[j].front(); R[j].pop();
            if (r < l) ans += qry(l - 1) - qry(r - 1);
            else ans += qry(r - 1) - qry(l);
            modify(l); modify(r);
        }
    }
	/*
    for (int i = 1; i <= n; i++) {
        if (qry(i)) {
            if (s[i] < 0) {
                int lpos = i, rpos = R[-s[i]].front();
                assert(L[-s[i]].front() == lpos);
                L[-s[i]].pop(), R[-s[i]].pop();

                ans += qry(rpos - 1) - qry(lpos);
                modify(lpos, -1), modify(rpos, -1);
            } else {
                int lpos = L[s[i]].front(), rpos = i;
                assert(R[s[i]].front() == rpos);
                L[s[i]].pop(), R[s[i]].pop();

                ans += qry(lpos - 1) - qry(rpos - 1);
                modify(lpos, -1), modify(rpos, -1);
            }
        }
    }
    */

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

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