Submission #352323

#	Time	Username	Problem	Language	Result	Execution time	Memory
352323		Sprdalo	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	466 ms	275308 KiB

shoes

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;


//Slozenost O(log n)

template<class T, int size>
struct fenwick {
    T a[size];
    /* precondition: pos > 0 */
    void add(int pos, const T& val) {
        while (pos < size) {
            a[pos] += val;
            pos += pos & -pos;
        }
    }
    T sum(int pos) {
        T ret = T();
        while (pos > 0) {
            ret += a[pos];
            pos -= pos & -pos;
        }
        return ret;
    }

    T sum(int l, int r){
        if (l>r) return 0;
        if (l == 1)
            return sum(r);
        return sum(r)-sum(l-1);
    }
};
fenwick<int,131072*2> drvo;

ll count_swaps(vi a){
    int n = a.size();

    queue<int> s[n+2], t[n+2];
    vi pos(n+1,-1);
    for (int i = 0; i < n; ++i){
        if (a[i]>0){
            int x = a[i];
            if (t[x].empty()){
                s[x].push(i);
                continue;
            }

            pos[i] = t[x].front();
            pos[pos[i]] = i;
            t[x].pop();
        } else {
            int x = -a[i];
            if (s[x].empty()){
                t[x].push(i);
                continue;
            }

            pos[i] = s[x].front();
            pos[pos[i]] = i;
            s[x].pop();
        }
    }

    vi vis(n+1, 0);
    ll sol = 0;

    for (int i = 1; i <= n; ++i)
        drvo.add(i,1);

    for (int i = 0; i < n; ++i){
        if (vis[i]) continue;

        sol += drvo.sum(i+2,pos[i]);

        if (a[i] > 0)
            ++sol;

        drvo.add(i+1,-1);
        drvo.add(pos[i]+1,-1);
        vis[i] = vis[pos[i]] = 1;
    }

    return sol;
}

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