Advertisement
AlexNeagu11

Untitled

Mar 30th, 2020
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. ifstream in("weekend.in");
  5. ofstream out("weekend.out");
  6. const int N = 200005;
  7. vector < int > fenw(N + 5), a(N + 5), ans;
  8. int n;
  9. void upd(int pos, int val) {
  10. for (; pos <= n; pos += pos & (-pos)) {
  11. fenw[pos] += val;
  12. }
  13. }
  14. int q(int pos) {
  15. int ans = 0;
  16. for (; pos; pos -= pos & (-pos)) {
  17. ans += fenw[pos];
  18. }
  19. return ans;
  20. }
  21. int main() {
  22. ios_base::sync_with_stdio(false);
  23. cin.tie(0);
  24. in >> n;
  25. for (int i = 1; i <= n; i++) {
  26. in >> a[i];
  27. a[i]++;
  28. upd(i, 1);
  29. }
  30. for (int i = n; i >= 1; i--) {
  31. int l = 1, r = n, pos;
  32. while(l <= r) {
  33. int mid = (l + r) / 2;
  34. int value = q(mid);
  35. if (value >= a[i]) {
  36. pos = mid;
  37. r = mid - 1;
  38. }
  39. else {
  40. l = mid + 1;
  41. }
  42. }
  43. ans.push_back(pos);
  44. upd(pos, -1);
  45. }
  46. for (int i = ans.size() - 1; i >= 0; i--) {
  47. out << ans[i] << '\n';
  48. }
  49. return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement