Submission #249270

#TimeUsernameProblemLanguageResultExecution timeMemory
249270muhammad_hokimiyonArranging Shoes (IOI19_shoes)C++14
10 / 100
1 ms384 KiB
#include "shoes.h" #include <bits/stdc++.h> #define fi first #define se second #define ll long long #define dl double long using namespace std; const int NN = 1e9 + 7; const int N = 2e6 + 7; const int M = 26; const ll mod = 1e9 + 7; const ll inf = 1e18 + 7; const dl rf = 1e-14; const int B = sqrt(N); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int d[N]; void upd( int x , int y ) { while( x < N ){ d[x] += y; x += x & -x; } } int get( int x ) { int cnt = 0; while( x > 0 ){ cnt += d[x]; x -= x & -x; } return cnt; } map < int , vector < int > > m; long long count_swaps(vector<int> s) { int n = (int)s.size(); ll ans = 0; for( int i = 1; i <= n; i++ ){ int x = -s[i - 1]; if( m[x].empty() ){ m[-x].push_back(i); }else{ int y = m[x].back(); m[x].pop_back(); ans += i - y - (x < 0) - get( i ) + get( y ); upd( i + 1 , -1 ); upd( y , 1 ); } } return ans; }
#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...