제출 #964456

#제출 시각아이디문제언어결과실행 시간메모리
964456beabossArranging Shoes (IOI19_shoes)C++17
50 / 100
213 ms280444 KiB
// Source: https://oj.uz/problem/view/IOI19_shoes // #include "bits/stdc++.h" using namespace std; #define s second #define f first #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef vector<pii> vpii; typedef vector<int> vi; #define FOR(i, a, b) for (int i = (a); i<b; i++) bool ckmin(int& a, int b){ return b < a ? a = b, true : false; } bool ckmax(int& a, int b){ return b > a ? a = b, true : false; } const int N = 1e5 + 10; struct BIT { private: int sz; vi bit; public: BIT(int n) : sz(n), bit(n + 1) {} void add(int pos, int val) { pos++; for (; pos <= sz; pos += (pos & -pos)) { bit[pos] += val; } } int pref(int ind) { ind++; int res = 0; for (; ind > 0; ind -= (ind & -ind)) res += bit[ind]; return res; } }; queue<int> l[N], r[N]; BIT bit(N); ll count_swaps(vi s) { int n = s.size(); FOR(i, 0, n) { if (s[i] < 0) l[-s[i]].push(i); else r[s[i]].push(i); bit.add(i, 1); } ll ans = 0; FOR(i, 0, n) { if (s[i] != 0) { int nxt; if (s[i] > 0) { nxt = l[s[i]].front(); ans++; } else { nxt = r[-s[i]].front(); s[i] = -s[i]; } r[s[i]].pop(); l[s[i]].pop(); bit.add(i, -1); s[i] = 0; s[nxt] = 0; bit.add(nxt, -1); ans += bit.pref(nxt); } } return ans; } // int main() { // ios::sync_with_stdio(false); // cin.tie(nullptr); // cout << count_swaps({2, 1, -1, -2}) << endl; // }
#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...