Submission #465346

#	Time	Username	Problem	Language	Result	Execution time	Memory
465346		marko	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	437 ms	202068 KiB

shoes

#include <bits/stdc++.h>

using namespace std;

struct Seg {
    vector<int> arr{};
    vector<int> a{};
    int m;
    Seg(vector<int> a) :a{a} { 
        const int n=a.size();
        m=1;
        do
        {
            m*=2;
        } while (m<n);

        arr.resize(2*m);
        build(1, 0, m-1);
    }

    void build (int index, int l, int r) {
        if (l==r) {
            arr[index]=(index-m<a.size())?a[index-m]: 0;
            return;
        }
        const int mid=(l+r)/2;
        build(2*index, l, mid);
        build(2*index+1, mid+1, r);
        arr[index]=arr[2*index]+arr[2*index+1];
    }

    int query_helper(int index, int l, int r, int cover_l, int cover_r) {
        if (r<cover_l) return 0;
        if (l>cover_r) return 0;
        if (l<=cover_l&&r>=cover_r) return arr[index];

        const int mid=(cover_l+cover_r)/2;
        return query_helper(2*index, l,r, cover_l, mid)+
        query_helper(2*index+1, l,r,mid+1, cover_r);
    }

    int query (int l, int r) {
        return query_helper(1, l, r, 0, m-1);
    }

    void update_helper(int index, int i, int x, int cover_l, int cover_r) {
        if (cover_l==cover_r) {
            arr[index]+=x;
            return;
        }

        auto mid=(cover_l+cover_r)/2;
        if (i<=mid) {
            update_helper(2*index, i, x, cover_l, mid);
        }
        else {
            update_helper(2*index+1, i, x, mid+1, cover_r);
        }

        arr[index]=arr[2*index]+arr[2*index+1];
    }

    void update(int i, int x) {
        update_helper(1, i, x, 0, m-1);
    }
};

int64_t count_swaps(vector<int> arr) {
    const int n=arr.size();
    vector<int> for_seg(n, 1);
    Seg seg{for_seg};

    unordered_map<int, deque<int>> indices{};

    int64_t ans{};
    for (auto i=0;i<arr.size();i++) {
        auto num=arr[i];
        auto opp=-num;

        if (indices[opp].empty())  {
            indices[num].push_front(i);
            continue;
        };
        auto j=indices[opp].back();
        indices[opp].pop_back();

        auto between=(i==j+1)?0:seg.query(j+1,i-1);
        ans+=between;
        if (num<0) ans++;

        seg.update(i, -1);
        seg.update(j, 1);
    }

    return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'void Seg::build(int, int, int)':
shoes.cpp:23:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             arr[index]=(index-m<a.size())?a[index-m]: 0;
      |                         ~~~~~~~^~~~~~~~~
shoes.cpp: In function 'int64_t count_swaps(std::vector<int>)':
shoes.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (auto i=0;i<arr.size();i++) {
      |                   ~^~~~~~~~~~~

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