Submission #1205063

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205063		tapilyoca	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	225 ms	164876 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using pll = pair<ll,ll>;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl;

void bruh(queue<ll> q) {
    while(!q.empty()) {
        cerr << q.front() << " ";
        q.pop();
    }
}

ll conv(ll x) {
    if(x < 0) return -x + 100000;
    return x;
}

class comp {
    public:
        bool operator()(pll a, pll b) {
            return a.first + a.second > b.first + b.second;
        }
};

struct Segtree { // range addition, point query so it doesnt matter lol   
    ll l, r;
    Segtree *lt, *rt;
    ll val;
    ll lazy;

    void combine() {
        val = min(lt->val,rt->val);
    }

    Segtree(ll lf, ll rf, vll &a) {
        l = lf, r = rf;
        lt = rt = nullptr;
        lazy = 0;
        if(l == r) {
            val = a[l];
            return;
        }
        ll mid = (l+r)>>1;
        lt = new Segtree(l,mid,a);
        rt = new Segtree(mid+1,r,a);
        combine();
    }

    void propagate() {
        if(lazy) {
            val += lazy;
            if(lt) {
                rt->lazy += lazy;
                lt->lazy += lazy;
            }
            lazy = 0;
        }
    }

    ll query(ll ql, ll qr) {
        propagate();
        if(qr < l or r < ql) return 1e18;
        if(ql <= l and r <= qr) return val;
        return min(lt->query(ql,qr), rt->query(ql,qr));
    }  

    void update(ll ul, ll ur) {
        propagate();
        if(ur < l or r < ul) return;
        if(ul <= l and r <= ur) {
            lazy++;
            propagate();
            return;
        }
        lt->update(ul,ur);
        rt->update(ul,ur);
        combine();
    }
};


long long count_swaps(std::vector<int> s) {
    ll n = s.size()>>1;
    ll out = 0;

    priority_queue<pll, vec<pll>, comp> pq;
    vec<queue<ll>> dists(200001);
    vll sta(2*n+1,0);


    
    for(ll j = 0; j < 2 * n; j++) {
        ll shoe = conv(s[j]);
        dists[shoe].push(j);
    }

    for(int i = 0; i <= n; i++) {
        while(!dists[i].empty()) {
            pq.push({dists[i].front(), dists[i+100000].front()});
            dists[i].pop();
            dists[i+100000].pop();            
        }
    }

    Segtree st(0,2*n-1,sta);

    ll mult = 0;
    while(!pq.empty()) {
        pll temp = pq.top();
        pq.pop();

        ll x = temp.first;
        ll y = temp.second;


        ll netX = x + st.query(x,x);
        ll netY = y + st.query(y,y);

        if(x > y) netX--;

        if(netX) st.update(0,x-1);
        if(netY) st.update(0,y-1);

        out += netX + netY - (2 * mult);

        mult += 2;
    }

    return out;
}



/*

4
2 -2 3 -3 2 -2 3 -3
output: 4

*/

/*

idea: essentially just moving things to the first slot.
greedily, best to move the negative first

*/

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