제출 #529858

#제출 시각아이디문제언어결과실행 시간메모리
529858buidangnguyen05Arranging Shoes (IOI19_shoes)C++14
10 / 100
1 ms308 KiB
/* input */ #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 10; int nxt[N], bit[N], n; bool solved[N]; map<int, queue<int>> q; void up(int x, int val) { while (x <= n) { bit[x] += val; x += x & (-x); } } int get(int x) { int ret = 0; while (x) { ret += bit[x]; x -= x & (-x); } return ret; } ll count_swaps(vector<int> v) { n = v.size(); v.insert(v.begin(), 0); for (int i = 1; i <= n; ++i) { if (q[-v[i]].size()) { int x = q[-v[i]].front(); q[-v[i]].pop(); nxt[x] = i; } else q[v[i]].push(i); } ll ret = 0; for (int i = 1; i <= n; ++i) if (!solved[i]) { int L = i + get(i), R = nxt[i] + get(nxt[i]); ret += R - L - 1 + (v[i] > 0); up(nxt[i], 1); solved[nxt[i]] = 1; } return ret; }
#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...