제출 #249276

#제출 시각아이디문제언어결과실행 시간메모리
249276muhammad_hokimiyonArranging Shoes (IOI19_shoes)C++14
100 / 100
556 ms148984 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 , deque < int > > m; long long count_swaps(vector<int> s) { int n = (int)s.size(); ll ans = 0; for( int i = 0; i < n; i++ ){ m[s[i]].push_back(i + 1); } vector < int > used(n + 1 , 0); for( int i = 0; i < n; i++ ){ if( used[i] )continue; int l = m[s[i]].front(); int r = m[-s[i]].front(); m[s[i]].pop_front(); m[-s[i]].pop_front(); ans += r - l - (s[i] < 0) - get( r ) + get( l ); upd( r , 1 ); used[l - 1] = used[r - 1] = 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...