제출 #529861

#제출 시각아이디문제언어결과실행 시간메모리
529861buidangnguyen05Arranging Shoes (IOI19_shoes)C++14
100 / 100
384 ms148876 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) { bit[x] += val; x -= x & (-x); } } int get(int x) { int ret = 0; while (x <= n) { 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]); //cout << i << " " << nxt[i] << " " << L << " " << R << "\n"; 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...