Approach
Sorting and greedy selection
For ABC331 C — Sum of Numbers Greater Than Me, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 53 lines of C++ from the credited upstream file abc331_c.cpp.
- The implementation visibly relies on sequence storage.
- 3 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <tuple>4#include <vector>5 6using namespace std;7 8bool comp(const tuple<unsigned long, unsigned int>& l,9 const tuple<unsigned long, unsigned int>& r) {10 return get<0>(l) > get<0>(r);11}12 13int main() {14 unsigned int n;15 cin >> n;16 17 vector<tuple<unsigned long, unsigned int>> a_idx; 18 for (unsigned int i = 0; i < n; i++) {19 unsigned long a;20 cin >> a;21 22 a_idx.push_back({a, i});23 }24 25 sort(a_idx.begin(), a_idx.end(), comp);26 27 vector<unsigned long> ans(n, 0);28 29 unsigned long prev = 0;30 unsigned long ans_tmp = 0;31 for (unsigned int i = 0; i < n; i++) {32 ans_tmp += prev;33 34 if (i > 0 && get<0>(a_idx[i]) == prev) {35 ans[get<1>(a_idx[i])] = ans[get<1>(a_idx[i - 1])];36 continue;37 }38 39 ans[get<1>(a_idx[i])] = ans_tmp;40 prev = get<0>(a_idx[i]);41 }42 43 for (unsigned int i = 0; i < n; i++) {44 if (i > 0) {45 cout << " ";46 }47 cout << ans[i];48 }49 50 cout << endl;51 52 return 0;53}