Submission #1011191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011191		rythm_of_knight	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	196 ms	277620 KiB

shoes

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

struct sgt {
    int n, ql, qr, qi, qx;
    vector <int> t;

    void init(int sz) {
        n = sz + 2;
        t.assign(n << 2, 0);
    }

    void update(int v, int l, int r) {
        if (l == r) {
            t[v] += qx;
            return;
        }
        int m = l + r >> 1;
        if (qi <= m)
            update(v << 1, l, m);
        else
            update(v << 1 | 1, m + 1, r);
        t[v] = t[v << 1] + t[v << 1 | 1];
    }

    void update(int l, int r) {
        qi = l, qx = 1;
        update(1, 0, n - 1);
        qi = r, qx = -1;
        update(1, 0, n - 1);
    }

    int get(int v, int l, int r) {
        // cout << l << ' ' << r << '\n' << flush;
        if (l > qi)
            return 0;
        if (r <= qi)
            return t[v];
        int m = l + r >> 1;
        return get(v << 1, l, m) + get(v << 1 | 1, m + 1, r);
    }
    int get(int i) {
        qi = i;
        return get(1, 0, n - 1);
    }
};

struct Fenwick{
    vector<int> tr;
    int sz;
    Fenwick(int N){
        tr.resize(N+1);
        sz=N;
    }
    void add(ll i, ll x){
        for (; i<=sz; i+=(-i&i)) tr[i]+=x;
    }
    ll get(ll i){
        ll sum=0;
        for (; i; i-=(i&-i)) sum+=tr[i];
        return sum;
    }
};
long long count_swaps(vector<int> s) {
	int n = s.size(), x;
	ll ans = 0, res = 0;
    vector <int> v = s;
    // cin >> n;
//    sgt st;
//    st.init(n);
    sgt st;
    st.init(n);
    Fenwick tr(n+2);
    vector <deque <int>> p(n + 1, deque <int>()), m(n + 1, deque <int>());
    for (int i = 0; i < n; i++) {
        // cin >> x;
        x = v[i];
        // cout << i << "i ";
        if (x > 0) {
            if (!m[x].empty()) {
                int it = m[x].front(); m[x].pop_front();
                int l = it + st.get(it), r = i;
                ans += r - l - 1;
                st.update(it, r + 1);
                // cout << it << ' ' << l << ' ' << r << '\n';
            } else {
                p[x].push_back(i);
            }
        } else {
            x = -x;
            if (!p[x].empty()) {
                int it = p[x].front(); p[x].pop_front();
                int l = it + st.get(it), r = i;
                ans += r - l;
                // cout << it << ' ' << l << ' ' << r << '\n';
                st.update(it, r + 1);
            } else {
                m[x].push_back(i);
            }
        }
    }
	return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'void sgt::update(int, int, int)':
shoes.cpp:20:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         int m = l + r >> 1;
      |                 ~~^~~
shoes.cpp: In member function 'int sgt::get(int, int, int)':
shoes.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int m = l + r >> 1;
      |                 ~~^~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:68:14: warning: unused variable 'res' [-Wunused-variable]
   68 |  ll ans = 0, res = 0;
      |              ^~~

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