Submission #143944

#	Time	Username	Problem	Language	Result	Execution time	Memory
143944		rama_pang	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	968 ms	151440 KiB

shoes

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

class FenwickTree{
  private:
    vector<ll> pairs;
    int N;
  public:
    FenwickTree(vector<ll> v) {
        pairs.resize(v.size() + 1);
        N = v.size();
        for (int i = 0; i < v.size(); i++) {
            update(i + 1, v[i]);
            if (i > 0) update(i + 1, -v[i - 1]);
        }
    }
    ll query(ll n) {
        n++;
        ll res = 0;
        for (ll i = n; i > 0; i -= i&-i) {
            res += pairs[i];
        }
        return res;
    }
    void update(ll n, ll val) {        
        for (ll i = n; i <= N; i += i&-i) {
            pairs[i] += val;
        }
    }
    void update2(ll le, ll n, ll val) {
        ll id = N - 1;
        ll l = 0, r = N - 1;
        while (l <= r) {
            ll mid = (l + r) / 2;
            if (query(mid) <= n) {
                l = mid + 1;
            } else {
                id = mid;
                r = mid - 1;
            }
        }
        id++;
        for (ll i = id; i <= N; i += i&-i) {
            pairs[i] -= val;
        }
        for (ll i = le; i <= N; i += i&-i) {
            pairs[i] += val;
        }
    }
};
void read(vector<pair<ll, ll>> &pairs, vector<int> &s) {
	map<ll, pair<ll, deque<ll>>> mp;
    for (ll i = 0; i < s.size(); i++) {
        mp[s[i]].first++;
        mp[s[i]].second.push_back(i);
        if (mp[s[i]].first >= 1 && mp[-s[i]].first >=1) {
            pairs.push_back({mp[s[i]].second.front(), mp[-s[i]].second.front()});
            if (s[i] > -s[i]) {
                swap(pairs.back().first, pairs.back().second);
            }
            mp[s[i]].first--; mp[-s[i]].first--;
            mp[s[i]].second.pop_front(); mp[-s[i]].second.pop_front();
        }
    }
    sort(pairs.begin(), pairs.end(), [](pair<ll, ll> &a, pair<ll, ll> &b){
        return min(a.first, a.second) < min(b.first, b.second);
    });
}
long long count_swaps(std::vector<int> s) {
    ll res = 0;
    vector<pair<ll, ll>> pairs; read(pairs, s);
    vector<ll> temp(s.size());
    for (auto i : pairs) {
        temp[i.first] = i.first;
        temp[i.second] = i.second;
    }
    FenwickTree value(temp);
    for (int k = 0, idx = 0; k < s.size(); k+=2, idx++) {
        ll ai = value.query(pairs[idx].first);
        ll aj = value.query(pairs[idx].second);
        res += ai + aj - k - k - 1 + (ai > aj);
        value.update2(1, ai, 1);
        value.update2(1, aj, 1);
    }
    return res;
}

Compilation message (stderr)

shoes.cpp: In constructor 'FenwickTree::FenwickTree(std::vector<long long int>)':
shoes.cpp:15:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < v.size(); i++) {
                         ~~^~~~~~~~~~
shoes.cpp: In function 'void read(std::vector<std::pair<long long int, long long int> >&, std::vector<int>&)':
shoes.cpp:56:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ll i = 0; i < s.size(); i++) {
                    ~~^~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:81:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0, idx = 0; k < s.size(); k+=2, idx++) {
                              ~~^~~~~~~~~~

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