Submission #314207

#	Time	Username	Problem	Language	Result	Execution time	Memory
314207		ShiftyBlock	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	428 ms	36472 KiB

shoes

#include <bits/stdc++.h>
#include <shoes.h>
using namespace std;
#define f first
#define s second
#define pii pair<int, int>
#define long long long
#define v vector
#define rep(i,a,b) for(int i=a; i<b; i++)

struct segtree{
    int N;
    vector<long> arr;
    segtree(int n){
        N=n;
        arr.assign(4*N, 0LL);
    }
    void update(int i, int val){
        update(i, val, 0, 0, N);
    }
    void update(int i, int val, int cur, int lx, int rx){
        if(rx-lx==1){
            arr[cur]=val; return;
        }
        int mid= (lx+rx)/2;
        if(mid>i) update(i, val, 2*cur+1, lx, mid);
        else update(i, val, 2*cur+2, mid, rx);
        arr[cur]= arr[cur*2+1]+arr[cur*2+2];
    }
    long sum (int l, int r){
        return sum(l,r,0, 0, N);
    }
    long sum(int l, int r, int cur, int lx, int rx){
        if(lx>=r || rx<=l) return 0;
        if(lx>=l && rx<=r) return arr[cur];
        int mid= (lx+rx)/2;
        return sum(l,r,2*cur+1, lx, mid)+sum(l,r,2*cur+2, mid, rx);
    }
};


int N;
map<int, set<int>> william_lin_is_a_hottie_and_gave_me_good_luck_on_this_problem_so_i_have_a_crush_on_him_ily_tmw;
long count_swaps(vector<int> arr){
	N=arr.size();
	for (int i = 0; i < N; ++i)
	{
		william_lin_is_a_hottie_and_gave_me_good_luck_on_this_problem_so_i_have_a_crush_on_him_ily_tmw[arr[i]].insert(i);
	}
	
	/*for(auto x= william_lin_is_a_hottie_and_gave_me_good_luck_on_this_problem_so_i_have_a_crush_on_him_ily_tmw.begin(); x!=william_lin_is_a_hottie_and_gave_me_good_luck_on_this_problem_so_i_have_a_crush_on_him_ily_tmw.end(); x++){
		cout<<x->f;
		for(int num: x->s){
			cout<<" "<<num;
		}
		cout<<endl;
	}
	*/
	
	long total=0;
	segtree st= segtree(N);
    for (int i = 0; i < N; ++i)
    {
    	if(arr[i]==0) continue;
    	auto endpt=william_lin_is_a_hottie_and_gave_me_good_luck_on_this_problem_so_i_have_a_crush_on_him_ily_tmw[-arr[i]].lower_bound(i);
    	int end=*endpt; 
    	william_lin_is_a_hottie_and_gave_me_good_luck_on_this_problem_so_i_have_a_crush_on_him_ily_tmw[-arr[i]].erase(end);
    	//cout<<end<<endl;
    	st.update(end, 1);
    	int free= st.sum(i, end);
    	if(arr[i]<0) total--;
    	arr[i]=0;
    	arr[end]=0;
    	total+=end-i-free;
    }
    return total;
}

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