Submission #873673

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
8736732023-11-15 13:04:27CutebolArranging Shoes (IOI19_shoes)C++17
100 / 100
406 ms31628 KiB
#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_pbds;
tree < int , null_type , less < int > , rb_tree_tag,tree_order_statistics_node_update > st ;
const int N = 2e6 + 5 ;
#define ll long long
map <ll , set <ll>> l , r ;
bool f[N] ;
long long count_swaps(vector<int> s) {
ll n = s.size() , ans = 0 ;
for ( int i = 0 ; i < n ; i ++ ){
if ( s[i] < 0 ) l[-s[i]].insert(i) ;
else r[s[i]].insert(i) ;
}
for ( int i = 0 ; i < n ; i ++ ){
if ( f[i] == 1 ){ st.erase(i); continue ;}
if ( s[i] < 0 ){
int ind = *r[-s[i]].begin() ;
r[-s[i]].erase(r[-s[i]].begin()) ;
l[-s[i]].erase(l[-s[i]].begin()) ;
int x = st.order_of_key(ind) ;
st.insert(ind) ;
ans += ind-i-1-x ;
f[ind] = 1 ;
}
else{
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...