제출 #723980

#제출 시각아이디문제언어결과실행 시간메모리
723980sandry24Arranging Shoes (IOI19_shoes)C++17
10 / 100
1 ms596 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pi; #define pb push_back #define mp make_pair #define f first #define s second const int sz = 100005; vector<int> BIT(sz); void add(int x, int delta){ for(; x <= sz; x += x & -x) BIT[x] += delta; } ll sum(int x){ ll res = 0; for(; x > 0; x -= x & -x) res += BIT[x]; return res; } int count_swaps(vi s){ map<int, vi> m; int n = s.size(); vector<bool> marked(n); for(int i = 0; i < n; i++) m[s[i]].pb(i); for(auto i : m) reverse(i.s.begin(), i.s.end()); ll ans = 0; for(int i = 0; i < n; i++){ if(marked[i]) continue; int need = -s[i]; int ind = m[need].back(); m[ind].pop_back(); m[s[i]].pop_back(); marked[i] = marked[ind] = 1; //cout << s[i] << ' ' << i << ' ' << ind << ' ' << sum(ind) << '\n'; ans += (ind - i - 1) - (sum(ind+1) - sum(i+1)); if(s[i] > 0) ans++; add(ind+1, 1); add(i+1, 1); //cout << ans << '\n'; } 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...