Submission #441804

#	Time	Username	Problem	Language	Result	Execution time	Memory
441804		QuantumK9	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	575 ms	148176 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define mp make_pair
 
map<int, queue<int> > rgt;

int LSO( int n ){ return ( n&(-n) ); }

class FT{
    private: vector<int> ft;
    public:
        FT( int n ){ ft.assign(n+1, 0); }
        int rsq(int b){
            int sum = 0;
            for( ; b; b -= LSO(b) ){ sum += ft[b];}
            return sum;
        }
        void adjust( int k, int v ){ for(; k < (int)ft.size(); k += LSO(k) ){ ft[k]+=v; } }
        //void report(){ for( int i = 0; i < ft.size(); i++ ){ cout << ft[i] << " "; } cout << endl; }
};
 
long long count_swaps(vector<int> s) {
	//num
	ll S = s.size();
	FT tre = FT(S);
 
	//iterate through s -- preprocess
	for( int i = 0; i < S; i++ ){
		rgt[ s[i] ].push(i+1);
		tre.adjust( i+1, 1 );
	}
 
	bool idim[S+2];
	memset( idim, true, sizeof idim );
 
	//process
	ll grand = 0;
	for( int i = 0; i < S; i++ ){
 
		if( idim[i+1] ){
 
			idim[i+1] = false;
			rgt[ s[i] ].pop();
			tre.adjust( i+1, -1 );
 
			//move partner 
			ll val = rgt[ -s[i] ].front();
			//for( int j = 0; j < val; j++ ){ grand += idim[j]; }
			grand += tre.rsq(val-1);
			idim[val] = false;
			rgt[ -s[i] ].pop();
			tre.adjust( val, -1);
 
			if( s[i] > 0 ){ grand++; }
		}
 
	}	
 
	return grand;
}

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