제출 #757765

#제출 시각아이디문제언어결과실행 시간메모리
757765taherArranging Shoes (IOI19_shoes)C++17
100 / 100
646 ms148832 KiB
#include <bits/stdc++.h> using namespace std; template <typename T> class fenwick { public: vector<T> fenw; int n; fenwick(int _n) : n(_n) { fenw.resize(n); } void modify(int x, T v) { while (x < n) { fenw[x] += v; x |= (x + 1); } } T get(int x) { T v{}; while (x >= 0) { v += fenw[x]; x = (x & (x + 1)) - 1; } return v; } }; long long count_swaps(vector<int> v){ int n = (int)v.size(); map<int , deque<int>> Mp; for(int i = 0 ; i < n ; i++){ Mp[v[i]].emplace_back(i); } fenwick<long long> q(n + 1); long long ans = 0; int coun = 1; int cnt = 0; for(int i = 0 ; i < n ; i++){ int cur = v[i]; if(Mp[cur].front() != i) continue; if(cur < 0){ cnt++; } int f = cur * -1; assert(f != cur); int idx = Mp[f].front(); Mp[cur].pop_front(); Mp[f].pop_front(); int now_f = q.get(idx); if(now_f + idx > cnt){ int g_idx = now_f + idx; ans += (g_idx - cnt); q.modify(idx + 1, -1); q.modify(0 , 1); } cnt = coun * 2; coun++; } 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...