Submission #1010690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010690		rythm_of_knight	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	58 ms	29748 KiB

shoes

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

using namespace std;

struct sgt {
    int n, ql, qr, qi, qx;
    vector <int> t;
    void init(int sz) {
        n = sz;
        t.assign((sz + 3) << 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 + 1, qx = -1;
        update(1, 0, n - 1);
    }

    int get(int v, int l, int r) {
        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);
    }
};

long long count_swaps(vector<int> s) {
    int n = s.size(), x;
	long long ans = 0;
    sgt st;
    st.init(n);
    vector <set <int>> p(n + 1, set <int>()), m(n + 1, set <int>());
    for (int i = 0; i < n; i++) {
    	x = s[i];
        if (x > 0) {
            if (!m[x].empty()) {
                auto it = m[x].begin();
                int l = *it + st.get(*it), r = i;
                ans += r - l - 1;
                m[x].erase(it);
                st.update(l, r);
            } else {
                p[x].insert(i);
            }
        } else {
            x = abs(x);
            if (!p[x].empty()) {
                auto it = p[x].begin();
                int l = *it + st.get(*it), r = i;
                ans += r - l;
                p[x].erase(it);
                st.update(l, r);
            } else {
                m[x].insert(i);
            }
        }
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'void sgt::update(int, int, int)':
shoes.cpp:19:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |         int m = l + r >> 1;
      |                 ~~^~~
shoes.cpp: In member function 'int sgt::get(int, int, int)':
shoes.cpp:39:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         int m = l + r >> 1;
      |                 ~~^~~

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