제출 #929029

#제출 시각아이디문제언어결과실행 시간메모리
929029AtabayRajabliArranging Shoes (IOI19_shoes)C++17
100 / 100
148 ms140204 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; const int MX = 2e5 + 5; int a[MX], used[MX]; void add(int ind, int x) { ind++; while(ind < MX) { a[ind] += x; ind += ind & -ind; } } int get(int ind) { ind++; int r = 0; while(ind > 0) { r += a[ind]; ind -= ind & -ind; } return r; } long long count_swaps(vector<int> s) { int N = s.size() / 2; queue<int> p[N + 1], n[N + 1]; for(int i = 0; i < N * 2; i++) { if(s[i] > 0)p[s[i]].push(i + 1); else n[-s[i]].push(i + 1); } long long ans = 0; for(int i = 0; i < N * 2; i++) { if(used[i + 1])continue; int x = p[abs(s[i])].front(); int y = n[abs(s[i])].front(); p[abs(s[i])].pop(); n[abs(s[i])].pop(); if(s[i] > 0) { ans += y - x - (get(y) - get(x)); add(y, 1); } else { ans += x - y - (get(x) - get(y)) - 1; add(x, 1); } used[y] = 1; used[x] = 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...