제출 #152219

#제출 시각아이디문제언어결과실행 시간메모리
152219johuthaArranging Shoes (IOI19_shoes)C++14
100 / 100
507 ms282124 KiB
#include "shoes.h" #include <vector> #include <queue> #include <algorithm> #include <iostream> #define int long long using namespace std; struct segtree { vector<int> table; void update(int k, int v, int l, int r, int pos) { if (l == r) { table[pos] = v; return; } if (k <= (l + r) / 2) update(k, v, l, (l + r) / 2, 2*pos + 1); else update(k, v, (l + r)/ 2 + 1, r, 2*pos + 2); table[pos] = table[2*pos + 1] + table[2*pos + 2]; } int query(int ql, int qr, int l, int r, int pos) { if (ql <= l && r <= qr) return table[pos]; if (ql > r || qr < l) return 0; return query(ql, qr, l, (l + r)/2, 2*pos + 1) + query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2); } }; long long count_swaps(vector<signed> s) { int n = s.size(); vector<queue<int>> poss(n + 1); vector<queue<int>> negs(n + 1); for (int i = 0; i < n; i++) { if (s[i] < 0) negs[-s[i]].push(i); else poss[s[i]].push(i); } vector<int> seq(n, -1); int curr = 0; for (int i = 0; i < n; i++) { if (seq[i] != -1) continue; int v = abs(s[i]); if (s[i] < 0) { seq[i] = curr; seq[poss[v].front()] = curr + 1; } else { seq[negs[v].front()] = curr; seq[i] = curr + 1; } poss[v].pop(); negs[v].pop(); curr += 2; } /* for (auto i : seq) cout << i << " "; cout << "\n"; */ int ssum = 0; segtree st; st.table.resize(4*n, 0); for (int i = 0; i < n; i++) { ssum += st.query(seq[i], n - 1, 0, n - 1, 0); st.update(seq[i], 1, 0, n - 1, 0); } return ssum; }
#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...