Submission #404057

#	Time	Username	Problem	Language	Result	Execution time	Memory
404057		dxz05	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	50 ms	40012 KiB

shoes

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

using namespace std;

typedef long long ll;

const int MAXN = 4e5 + 6e3;

int n;

vector<int> positions[MAXN];
int szz[MAXN];

inline int code(int val){
    return (val < 0 ? -val : val + 200000);
}

struct SegTree{
    int size = 1;

    struct node{
        int val = 0;
        bool isAdded = false;
        int AddedValue = 0;
        node(int x, bool y, int z){
            val = x, isAdded = y, AddedValue = z;
        }
        node(){};
    };

    vector<node> tree;

    bool flag;

    void build(int v, int tl, int tr, vector<int>&a){
        if (tl == tr){
            tree[v].val = (!flag ? 1 : tl < a.size() ? a[tl] : 0);
            return;
        }
        int tm = (tl + tr) >> 1;
        build(v + v + 1, tl, tm, a);
        build(v + v + 2, tm + 1, tr, a);
        tree[v].val = tree[v + v + 1].val + tree[v + v + 2].val;
    }

    void init(vector<int>&a, bool _flag){
        flag = _flag;
        while (size <= a.size()) size <<= 1;
        tree.resize(2 * size);
        build(0, 0, size - 1, a);
    }

    void propagate(int v, int tl, int tr){
        if (!tree[v].isAdded || tl == tr) return;

        int tm = (tl + tr) >> 1;

        tree[v + v + 1].val += tree[v].AddedValue * (tm - tl + 1);
        tree[v + v + 1].AddedValue += tree[v].AddedValue;

        tree[v + v + 2].val += tree[v].AddedValue * (tr - tm);
        tree[v + v + 2].AddedValue += tree[v].AddedValue;

        tree[v + v + 1].isAdded = tree[v + v + 2].isAdded = true;
        tree[v].isAdded = false;

        tree[v].AddedValue = 0;
    }

    void Range_Add(int v, int tl, int tr, int l, int r, int val){
        if (l <= tl && tr <= r){
            tree[v].isAdded = true;
            tree[v].val += (tr - tl + 1) * val;
            tree[v].AddedValue += val;
            return;
        }
        if (tl > r || tr < l) return;

        propagate(v, tl, tr);

        int tm = (tl + tr) >> 1;
        Range_Add(v + v + 1, tl, tm, l, r, val);
        Range_Add(v + v + 2, tm + 1, tr, l, r, val);

        tree[v].val = tree[v + v + 1].val + tree[v + v + 2].val;
    }

    void Range_Add(int l, int r, int val){
        Range_Add(0, 0, size - 1, l, r, val);
    }

    void update(int v, int tl, int tr, int pos, int val){
        if (tl == tr){
            tree[v].val = val;
            return;
        }

        int tm = (tl + tr) >> 1;
        if (pos <= tm) update(v + v + 1, tl, tm, pos, val); else
            update(v + v + 2, tm + 1, tr, pos, val);

        tree[v].val = tree[v + v + 1].val + tree[v + v + 2].val;
    }

    void update(int pos, int val){
        update(0, 0, size - 1, pos, val);
    }

    pair<int, int> find_kth(int v, int tl, int tr, int k){
        if (tl == tr) return make_pair(tree[v].val, tl);
        int tm = (tl + tr) >> 1;
        if (tree[v + v + 1].val >= k) return find_kth(v + v + 1, tl, tm, k); else
            return find_kth(v + v + 2, tm + 1, tr, k - tree[v + v + 1].val);
    }

    pair<int, int> find_kth(int k){
        return find_kth(0, 0, size - 1, k);
    }

    int get(int v, int tl, int tr, int l, int r){
        if (l <= tl && tr <= r) return tree[v].val;
        if (tl > r || tr < l) return 0;
        propagate(v, tl, tr);
        int tm = (tl + tr) >> 1;
        return get(v + v + 1, tl, tm, l, r) + get(v + v + 2, tm + 1, tr, l, r);
    }

    int get(int l, int r){
        return get(0, 0, size - 1, l, r);
    }

    int get(int pos){
        return get(pos, pos);
    }

};

SegTree st[MAXN];

long long count_swaps(vector<int> a) {
    n = a.size();

    vector<int> perm(n);
    for (int i = 0; i < n; i++){
        positions[code(a[i])].push_back(i);
        perm[i] = i;
    }

    st[0].init(perm, true);
    for (int i = 1; i < MAXN; i++){
        st[i].init(positions[i], false);
        szz[i] = positions[i].size();
    }

    vector<bool> used(n, false);

    ll ans = 0;

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

        int x = code(a[i]), y = code(-a[i]);

        int pos1 = st[0].get(i), pos2 = -1;
        int index1 = st[x].find_kth(1).second, index2 = 0;

        int l = 1, r = szz[y];
        while (l <= r){
            int mid = (l + r) >> 1;
            pair<int, int> p = st[y].find_kth(mid);
           //cout << p.second << endl;
            int ind = positions[y][p.second];

            if (st[0].get(ind) >= pos1){
                pos2 = ind;
                index2 = p.second;
                r = mid - 1;
            } else l = mid + 1;
        }

        //cout << pos1 << ' ' << pos2 << endl;
        //cout << index1 << ' ' << index2 << endl;

        st[x].update(index1, 0);
        st[y].update(index2, 0);
        szz[x]--;
        szz[y]--;

        ans += pos2 - pos1 - 1 + (a[i] > 0);

        used[positions[y][index2]] = true;

        st[0].Range_Add(index1 + 1, index2 - 1, 1);

    }

    return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'void SegTree::build(int, int, int, std::vector<int>&)':
shoes.cpp:38:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             tree[v].val = (!flag ? 1 : tl < a.size() ? a[tl] : 0);
      |                                        ~~~^~~~~~~~~~
shoes.cpp: In member function 'void SegTree::init(std::vector<int>&, bool)':
shoes.cpp:49:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while (size <= a.size()) size <<= 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