Submission #437909

#	Time	Username	Problem	Language	Result	Execution time	Memory
437909		dajma	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	979 ms	152648 KiB

shoes

#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
#define sz(x) (int)(x).size()
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
#define endl '\n'
// remove above line when interactive
/*
Some Notes:

-2 2 -2 2 -2 2
0 1 2 3 4 5
 0 1  0 1 


2 2 2 -2 -2 -2
3     4


*/
template <typename TYPE>
class FenwickTree
{
    private:
        TYPE * add;
        TYPE * mul;
        size_t length;

        // performs the actual range update
        void range_update_helper(size_t pos, TYPE mulfact, TYPE addfact)
        {
            pos += 1;
            while(pos <= length)
            {
                mul[pos - 1] += mulfact;
                add[pos - 1] += addfact;
                pos += pos & -pos;
            }
        }

    public:
        // constructor with vector
        FenwickTree(std::vector<TYPE>& v)
        {
            length = v.size();
            add = new TYPE[length];
            mul = new TYPE[length];

            // initialize
            for(size_t i = 0; i < length; ++i)
            {
                add[i] = 0;
                mul[i] = 0;
            }

            // point-wise updates
            for(size_t i = 0; i < length; ++i)
            {
                point_update(i, v[i]);
            }
        }

        // constructor with an array v[] of given size input_length
        FenwickTree(TYPE v[], int input_length)
        {
            length = input_length;
            add = new TYPE[length];
            mul = new TYPE[length];

            // initialize
            for(size_t i = 0; i < length; ++i)
            {
                add[i] = 0;
                mul[i] = 0;
            }

            // point-wise updates
            for(size_t i = 0; i < length; ++i)
            {
                point_update(i, v[i]);
            }
        }

        // add value 'val' to position i in a[0..length - 1]
        void point_update(size_t i, TYPE val)
        {
            range_update(i, i, val);
        }

        // add value 'val' to postions a[i..j]
        void range_update(size_t i, size_t j, TYPE val)
        {
            if(i < 0 or j < i or j >= length)
            {
                throw std::invalid_argument("subarray range invalid.");
            }
            else
            {
                range_update_helper(i, val, -val * ((TYPE) i - 1));
                range_update_helper(j, -val, val * j);
            }
        }

        // find sum of range a[i..j] (both inclusive)
        TYPE range_sum(size_t i, size_t j)
        {
            if(i < 0 or j < i or j >= length)
            {
                throw std::invalid_argument("subarray range invalid.");
            }
            else
            {
                if(i > 0)
                {
                    return prefix_sum(j) - prefix_sum(i - 1);
                }
                else
                {
                    return prefix_sum(j);
                }
            }
        }

        // find sum of range a[0..i] (both inclusive)
        TYPE prefix_sum(size_t i)
        {
            TYPE mulfact = 0;
            TYPE addfact = 0;

            size_t startindex = i;
            i += 1;

            while(i > 0)
            {
                addfact += add[i - 1];
                mulfact += mul[i - 1];
                i = i & (i - 1);
            }

            return ((TYPE) startindex) * mulfact + addfact;
        }

        // returns the value of a[i]
        TYPE point_sum(size_t i)
        {
            if(i < 0 or i >= length)
            {
                throw std::invalid_argument("invalid array index.");
            }
            else
            {
                return range_sum(i, i);
            }
        }
};

ll count_swaps(vector<int> t) {
    int n = sz(t);
    map<int, deque<int>> mp;
    for (int i = 0; i < n; i++) {
    	int x = t[i];
    	mp[x].push_back(i);
    }
    vector<int> v(n, -1);
    int cur = 0;
    for (int i = 0; i < n; i++) {
    	if (v[i] != -1) continue;
    	if (t[i] < 0) {
    		v[i] = cur++;
    		mp[t[i]].pop_front();
    		v[mp[-t[i]].front()] = cur++;
    		mp[-t[i]].pop_front();
    	}
    	else {
    		v[i] = cur + 1;
    		mp[t[i]].pop_front();
    		v[mp[-t[i]].front()] = cur;
    		mp[-t[i]].pop_front();
    		cur += 2;
    	}
    }
    debug() << imie(v);
    ll inversions = 0;
    vector<ll> c(n);
    FenwickTree<ll> fn(c);
    for (int i = 0; i < n; i++) {
    	ll curx = v[i];
    	ll cnt = curx + 1 <= n - 1 ? fn.range_sum(curx + 1, n - 1) : 0;
    	inversions += cnt;
    	fn.point_update(curx, 1LL);
    }
    return inversions;
}

/*signed main(){
    fastio
    assert(count_swaps({-2, 2, 2, -2, -2, 2}) == 1);
    assert(count_swaps({2, 1, -1, -2}) == 4);
    return 0; 
}*/

Compilation message (stderr)

shoes.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

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