Submission #713998

#	Time	Username	Problem	Language	Result	Execution time	Memory
713998		europium	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	639 ms	150112 KiB

shoes

#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <iterator>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <queue>
#include <unordered_set>
using namespace std;

using ll = long long;

struct segtree{
    int size;
    vector <int> values;

    int NEUTRAL_ELEMENT = 0;

    int merge(int a, int b){
        return a + b;
    }

    void init(int n){
        size = 1;
        while (size < n) size *= 2;
        values.resize(2 * size, 0);
    }

    void build(vector<int> &a, int x, int lx, int rx){
        if (rx - lx == 1){
            if (lx < a.size()){
                values[x] = a[lx];
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);
        values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
    }

    void build(vector<int> &a){
        build(a, 0, 0, size);
    }

    void set(int i, int v, int x, int lx, int rx){
        if (rx - lx == 1){
            values[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m){
            set(i, v, 2 * x + 1, lx, m);
        }
        else{
            set(i, v, 2 * x + 2, m, rx);
        }
        values[x] = merge(values[2 * x + 1], values[2 * x + 2]);
    }

    void set(int i, int v){
        set(i, v, 0, 0, size);
    }

    int calc(int l, int r, int x, int lx, int rx){
        if (lx >= r || l >= rx) return NEUTRAL_ELEMENT;
        if (lx >= l && rx <= r) return values[x];
        int m = (lx + rx) / 2;
        int s1 = calc(l, r, 2 * x + 1, lx, m);
        int s2 = calc(l, r, 2 * x + 2, m, rx);
        return merge(s1, s2);
    }

    int calc(int l, int r){
        return calc(l, r, 0, 0, size);
    }
};


ll count_swaps(vector<int> a) {
	ll n = a.size();
	ll ans = 0;

	segtree st;
	st.init(n);

	vector<int> used(n, 1);
	st.build(used);

	map<int,queue<int>> pos;

	for (int i = 0; i < n; i++){
		pos[a[i]].push(i + 1);
	}

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

		int j = pos[-a[i]].front() - 1;

		pos[-a[i]].pop();
		pos[a[i]].pop();

		st.set(i, 0);
		st.set(j, 0);

		used[i] = 0;
		used[j] = 0;

		int val = st.calc(i, j);

		if (a[i] > 0) ans += val + 1;
		else ans += val;
	}

	return ans;
}

Compilation message (stderr)

shoes.cpp: In member function 'void segtree::build(std::vector<int>&, int, int, int)':
shoes.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if (lx < a.size()){
      |                 ~~~^~~~~~~~~~

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