#include <algorithm> #include <iostream> #include <vector> #include <cassert> #include <climits> #include <numeric> struct Change { int begin, val, right; }; std::vector<std::vector<Change>> columns; std::vector<Change*> pairsSorted; std::vector<Change> result; int getBegin(const std::vector<Change>& vec, size_t i) { return (i < vec.size() ? vec[i].begin : INT_MAX); } std::vector<Change> merge(std::vector<Change>& left, std::vector<Change>& right) { // Aggregate pairs Change elem{0, left[0].val, right[0].val}; std::vector<Change> pairs; pairs.push_back(elem); size_t l = 0, r = 0; while (l+1 < left.size() || r+1 < right.size()) { if (getBegin(left, l+1) < getBegin(right, r+1)) { elem.begin = left[++l].begin; elem.val = left[l].val; } else { elem.begin = right[++r].begin; elem.right = right[r].val; } pairs.push_back(elem); } // Sort pairs pairsSorted.clear(); for (auto& p : pairs) { pairsSorted.push_back(&p); } sort(pairsSorted.begin(), pairsSorted.end(), [](Change* l, Change* r)->bool { return l->val < r->val || (l->val == r->val && l->right < r->right); }); // Enumerate int val1 = -1, val2 = -1, num = 0; for (auto cur : pairsSorted) { num += (cur->val != val1 || cur->right != val2 ? 1 : 0); val1 = cur->val; val2 = cur->right; cur->val = num; } return pairs; } std::vector<Change> solve(int begin, int end) { if (begin+1 == end) { return columns[begin]; } int mid = (begin+end) / 2; auto left = solve(begin, mid), right = solve(mid, end); return merge(left, right); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int nCols, nLines; std::cin >> nCols >> nLines; columns.resize(nCols); for (auto& col : columns) { int val; std::cin >> val; col.push_back({ 0, val, 0 }); } for (int line = 1; line < nLines; line++) { int col, val; std::cin >> col >> val; columns[col-1].push_back({ line, val, 0 }); } result = solve(0, nCols); // Print std::vector<int> order(nLines); std::iota(order.begin(), order.end(), 0); std::stable_sort(order.begin(), order.end(), [](int l, int r)->bool { return result[l].val < result[r].val; }); for (int x : order) { std::cout << x+1 << " "; } std::cout << std::endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | #include <algorithm> #include <iostream> #include <vector> #include <cassert> #include <climits> #include <numeric> struct Change { int begin, val, right; }; std::vector<std::vector<Change>> columns; std::vector<Change*> pairsSorted; std::vector<Change> result; int getBegin(const std::vector<Change>& vec, size_t i) { return (i < vec.size() ? vec[i].begin : INT_MAX); } std::vector<Change> merge(std::vector<Change>& left, std::vector<Change>& right) { // Aggregate pairs Change elem{0, left[0].val, right[0].val}; std::vector<Change> pairs; pairs.push_back(elem); size_t l = 0, r = 0; while (l+1 < left.size() || r+1 < right.size()) { if (getBegin(left, l+1) < getBegin(right, r+1)) { elem.begin = left[++l].begin; elem.val = left[l].val; } else { elem.begin = right[++r].begin; elem.right = right[r].val; } pairs.push_back(elem); } // Sort pairs pairsSorted.clear(); for (auto& p : pairs) { pairsSorted.push_back(&p); } sort(pairsSorted.begin(), pairsSorted.end(), [](Change* l, Change* r)->bool { return l->val < r->val || (l->val == r->val && l->right < r->right); }); // Enumerate int val1 = -1, val2 = -1, num = 0; for (auto cur : pairsSorted) { num += (cur->val != val1 || cur->right != val2 ? 1 : 0); val1 = cur->val; val2 = cur->right; cur->val = num; } return pairs; } std::vector<Change> solve(int begin, int end) { if (begin+1 == end) { return columns[begin]; } int mid = (begin+end) / 2; auto left = solve(begin, mid), right = solve(mid, end); return merge(left, right); } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int nCols, nLines; std::cin >> nCols >> nLines; columns.resize(nCols); for (auto& col : columns) { int val; std::cin >> val; col.push_back({ 0, val, 0 }); } for (int line = 1; line < nLines; line++) { int col, val; std::cin >> col >> val; columns[col-1].push_back({ line, val, 0 }); } result = solve(0, nCols); // Print std::vector<int> order(nLines); std::iota(order.begin(), order.end(), 0); std::stable_sort(order.begin(), order.end(), [](int l, int r)->bool { return result[l].val < result[r].val; }); for (int x : order) { std::cout << x+1 << " "; } std::cout << std::endl; return 0; } |