Submission #297255

#	Time	Username	Problem	Language	Result	Execution time	Memory
297255		infinite_iq	Arranging Shoes (IOI19_shoes)	C++14	15 / 100	681 ms	44664 KiB

shoes

#include <bits/stdc++.h>
using namespace std ;
#define mid (l+r)/2
#define le node*2
#define ri node*2+1
#define C continue 
#define pb push_back 
#define ins insert 
typedef vector <int> vi ;
typedef long long ll ;
#include "shoes.h"
int N , n ;
vi  v [200009] ;
int a [200009] ;
set < int > comp ;
map < int , int > id12 , id21 ;
int tree [800009] ;
void build ( int node , int l , int r ) {
        if ( l == r ) {
                tree [node] = 1 ;
                return ;
        }
        build ( le , l , mid ) ;
        build ( ri , mid + 1 , r ) ;
        tree [node] = tree [le] + tree [ri] ;
}
void upd ( int node , int l , int r , int id ) {
        if ( l == r ) {
                tree [node] = 0 ;
                return ;
        }
        if ( id <= mid ) upd ( le , l , mid , id ) ;
        else upd ( ri , mid + 1 , r , id ) ;
        tree [node] = tree [le] + tree [ri] ;
}
int query ( int node , int l , int r , int s , int e ) {
        if ( s > r || e < l || s > e ) return 0 ;
        if ( s <= l && e >= r ) return tree [node] ;
        return query ( le , l , mid , s , e ) + query ( ri , mid + 1 , r , s , e ) ;
}
long long count_swaps ( vi s ) {
        n = s.size () ;
        for ( int i = 0 ; i < n ; i ++ ) {
                comp .ins ( s [i] ) ;
        }
        for ( auto u : s ) {
                id12 [u] = N ;
                id21 [N] = u ;
                N ++ ;
        }
        for ( int i = 0 ; i < n ; i ++ ) {
                a [i] = id12 [ s [i] ] ;
        }
        for ( int i = n-1 ; i >= 0 ; i -- ) {
                v [ a [i] ] .pb ( i ) ;
        }
        build ( 1 , 0 , n-1 ) ;
        ll ans = 0 ;
        for ( int i = 0 ; i < n ; i ++ ) {
                int x = a [i] ;
                int y = id12 [-id21[x]] ;
                if ( v [x] .back () != i ) C ;
                int l = i + 1 , r = v [y] .back () - 1 ;
                ans += query ( 1 , 0 , n -1 , l , r ) ;
                ans += ( x > y ) ;
                upd ( 1 , 0 , n -1 , r + 1 ) ;
          v [x] .pop_back () ;
                v [y] .pop_back () ;

        }
        return ans ;
}

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