제출 #712975

#제출 시각아이디문제언어결과실행 시간메모리
712975mseebacherArranging Shoes (IOI19_shoes)C++17
100 / 100
137 ms54188 KiB
//#include <bits/stdc++.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <string> #include <vector> #include <cmath> #include <cstring> #include <algorithm> #include <iomanip> #include <map> #include <set> #include <stack> #include <queue> #include <functional> #include <iostream> #include <fstream> #include <string> using namespace std; #define mp make_pair #define f first #define s second #define pb push_back typedef long long ll; typedef long double lld; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; const lld pi = 3.14159265358979323846; #define MAXI (int)1e5 #define LSOne(S) ((S) & -(S)) #define MSB(S) __builtin_clz(S) vector<int> ad[MAXI]; vector<ll> ft; ll sumFT(int index){ ll sum = 0; while(index > 0){ sum+= ft[index]; index -= LSOne(index); } return sum; } int getval(int index){ int x = sumFT(index)-sumFT(index-1); if(x == 0) return 1; else return -1; } void updateFT(int index, ll val){ while(index < (int)ft.size()){ ft[index] += val; index += LSOne(index); } } long long count_swaps(vector<int> a){ int n = a.size(); vector<set<int>> left(2*n+1); vector<set<int>> right(2*n+1); vector<bool> marked(2*n,0); ll ans = 0; for(int i = 1;i<=n;i++){ if(a[i-1] < 0){ int x = a[i-1]*-1; left[x].insert(i); }else right[a[i-1]].insert(i); } ft.assign(n+1,0); for(int i = 1;i<=n;i++){ updateFT(i,1); } int links,rechts; for(int i = 0;i<n;i++){ if(marked[i]) continue; links = i+1; if(a[i] < 0) { rechts = *right[abs(a[i])].begin(); ans--; }else{ rechts = *left[a[i]].begin(); } ans += sumFT(rechts)-sumFT(links); updateFT(links,-1); updateFT(rechts,-1); right[abs(a[i])].erase(*right[abs(a[i])].begin()); left[abs(a[i])].erase(*left[abs(a[i])].begin()); marked[links-1] = 1; marked[rechts-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...