제출 #1254956

#제출 시각아이디문제언어결과실행 시간메모리
1254956ciao_gioArranging Shoes (IOI19_shoes)C++20
50 / 100
134 ms138928 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; struct Segment { int n; vector<int> t; Segment(int _n) : n(_n), t(2 * n, 0) {} void update(int i, int x = 1) { for (t[i += n] += x; i > 1; i >>= 1) { t[i >> 1] = t[i] + t[i ^ 1]; } } int query(int l, int r) { int ans = 0; for (l += n, r += n; l < r; l >>= 1, r >>= 1) { if (l & 1) ans += t[l++]; if (r & 1) ans += t[--r]; } return ans; } }; long long count_swaps(std::vector<int> s) { int n = s.size() / 2; vector<queue<int>> nxt(2 * n + 1); for (int i = 0; i < 2 * n; i++) { nxt[n + s[i]].push(i); } Segment t(2 * n); vector<bool> mvd(2 * n, false); int ans = 0; for (int i = 0; i < 2 * n; i++) { if (mvd[i]) continue; int j = nxt[n - s[i]].front(); nxt[n + s[i]].pop(); nxt[n - s[i]].pop(); ans += j - i - t.query(i, j + 1) - (s[i] < 0); t.update(j); mvd[j] = true; } 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...