제출 #855819

#제출 시각아이디문제언어결과실행 시간메모리
855819dong_liuArranging Shoes (IOI19_shoes)C++17
100 / 100
53 ms14672 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define ar array #define sz(v) int(v.size()) typedef long long ll; typedef pair<int, int> pi; struct FT { vector<int> t; FT(int n) : t(n,0) {} void upd(int i, int x) { while (i < sz(t)) { t[i] += x; i |= i+1; } } int qry(int i) { int x = 0; while (i >= 0) { x += t[i]; i &= i+1, i--; } return x; } int qry(int l, int r) { return qry(r)-qry(l-1); } }; ll count_swaps(vector<int> v) { int n = sz(v) / 2; vector<vector<int>> L(n), R(n); for (int i = 0; i < n*2; i++) if (v[i]<0) L[abs(v[i])-1].push_back(i); else R[abs(v[i])-1].push_back(i); vector<pi> f; for (int a = 0; a < n; a++) { assert(sz(L[a]) == sz(R[a])); for (int j = 0; j < sz(L[a]); j++) f.push_back({L[a][j],R[a][j]}); } ll ans = 0; for (auto &[l,r] : f) { if (l>r) { swap(l,r); ans++; } } sort(f.begin(), f.end()); FT ft(n*2); for (auto [l,r] : f) { ans += ft.qry(l,n*2-1)+ft.qry(r,n*2-1); ft.upd(r,1); } return ans; } // int main() { // cout << count_swaps({2,1,-1,-2}) << '\n'; // cout << count_swaps({-2,2,2,-2,-2,2}) << '\n'; // }
#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...