Untitled
unknown
c_cpp
a year ago
3.0 kB
6
Indexable
#include <bits/stdc++.h> using namespace std; // left and right are inclusive and 0-indexed vector<pair<int,int>> solvebackwards(map<pair<int,int>,int>& m, const vector<pair<int,int>>& v, int left, int right) { int numstuff = right - left + 1; vector<pair<int,int>> ret(numstuff); if (numstuff == 0) { return ret; } if (numstuff == 1) { ret[0] = v[left]; return ret; } vector<pair<int,int>> v_l = solvebackwards(m, v, left, left + numstuff/2 - 1); vector<pair<int,int>> v_r = solvebackwards(m, v, left + numstuff/2, right); int vl_size = v_l.size(); int vr_size = v_r.size(); int p1 = vl_size-1; int p2 = vr_size-1; while (p2 >= 0 && p1 >= 0) { if (v_l[p1].second < v_r[p2].second) { p1--; } else { m[v_r[p2]] += p1 + 1; p2--; } } int l = 0, r = 0; int i = 0; while (l < vl_size || r < vr_size) { if (l == vl_size) { ret[i] = v_r[r]; r++; } else if (r == vr_size) { ret[i] = v_l[l]; l++; } else if (v_r[r].second > v_l[l].second) { ret[i] = v_r[r]; r++; } else { ret[i] = v_l[l]; l++; } i++; } return move(ret); } vector<pair<int,int>> solve(map<pair<int,int>,int>& m, const vector<pair<int,int>>& v, int left, int right) { int numstuff = right - left + 1; vector<pair<int,int>> ret(numstuff); if (numstuff == 0) { return ret; } if (numstuff == 1) { ret[0] = v[left]; return ret; } vector<pair<int,int>> v_l = solve(m, v, left, left + numstuff/2 - 1); vector<pair<int,int>> v_r = solve(m, v, left + numstuff/2, right); int vl_size = v_l.size(); int vr_size = v_r.size(); int p1 = vl_size-1; int p2 = vr_size-1; while (p2 >= 0 && p1 >= 0) { if (v_l[p1].second > v_r[p2].second) { p1--; } else { m[v_r[p2]] += p1 + 1; p2--; } } int l = 0, r = 0; int i = 0; while (l < vl_size || r < vr_size) { if (l == vl_size) { ret[i] = v_r[r]; r++; } else if (r == vr_size) { ret[i] = v_l[l]; l++; } else if (v_r[r].second < v_l[l].second) { ret[i] = v_r[r]; r++; } else { ret[i] = v_l[l]; l++; } i++; } return move(ret); } int main() { int n, x, y; cin >> n; vector<pair<int,int>> v(n); map<pair<int,int>,int> m; for (int i = 0; i < n; i++) { cin >> x >> y; pair<int,int> temp = make_pair(x, y); v[i] = temp; m[temp] = 0; } vector<pair<int,int>> orig(v); sort(v.begin(), v.end()); solve(m, v, 0, v.size()-1); sort(v.rbegin(), v.rend()); solvebackwards(m, v, 0, v.size()-1); for (auto& p : orig) { cout << m[p] << " "; } }
Editor is loading...
Leave a Comment