Submission #730450

#	Time	Username	Problem	Language	Result	Execution time	Memory
730450		Skywk	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	153 ms	139744 KiB

shoes

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

using namespace std;

class FenwickTree{
    vector<int> bit; int N; 
public:
    FenwickTree(int n) : N(n){bit.resize(N+1);};
    void update(int i, int x){
        for(; i<=N; i+=(i&(-i))) bit[i] += x;
    }
    int query(int i){
        int res = 0;
        for(; i>0; i-=(i&(-i))) res += bit[i];
        return res;
    }
    int query(int l, int r){
        return query(r) - query(l-1);
    }
};

const int MAXN = 1e5;
queue<int> _pos[2*(MAXN + 1)];
queue<int> *pos = _pos + (MAXN + 1);
#define left_shoe(x) 2*x + 1
#define right_shoe(x) 2*x + 2

long long count_swaps(vector<int> s) {
	int N = s.size();
    FenwickTree ft(N << 1);
    long long cnt_swaps = 0;
    for(int i=0; i<N; i++){
        if(pos[-s[i]].empty()){
            pos[s[i]].push(i);
            ft.update(left_shoe(i), 1);
        }
        else{
            int j = pos[-s[i]].front();
            pos[-s[i]].pop();
            int k = ft.query(right_shoe(j), left_shoe(i));
            if(s[i] < 0) k++;
            cnt_swaps += k;
            ft.update(right_shoe(j), 1);
        }
    }
    return cnt_swaps;
}

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