Advertisement
Guest User

Untitled

a guest
Jan 28th, 2020
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <string>
  6. #include <set>
  7. #include <cstdio>
  8. #include <iomanip>
  9. #include <map>
  10. #include <stdio.h>
  11. #include <math.h>
  12. #include <queue>
  13. #include <random>
  14. #define int long long
  15. using namespace std;
  16. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  17.  
  18.  
  19. int gcd(int a, int b) { return b ? a : gcd(b, a % b); }
  20.  
  21. int toNum(char s) {
  22. return s - 'a';
  23. }
  24.  
  25. const int inf = 1 << 31 - 1;
  26. const int n = 100001;
  27. //#pragma GCC optimize("Ofast")
  28. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  29.  
  30. int tree[400008];
  31. int a[100002];
  32. int k, x, y,siz,q;
  33.  
  34. void build(int v, int left, int right) {
  35. if (left + 1 == right)
  36. tree[v] = 1;
  37. else {
  38. int mid = (left + right) / 2;
  39. build(2 * v, left, mid);
  40. build(2 * v + 1, mid, right);
  41. tree[v] = tree[2 * v] + tree[2 * v + 1];
  42. }
  43. }
  44.  
  45.  
  46. void update(int v, int left, int right, int pos, int kek) {
  47. if (left + 1 == right)
  48. tree[v] = kek;
  49. else {
  50. int mid = (left + right) / 2;
  51. if (pos < mid)
  52. update(2 * v, left, mid, pos, kek);
  53. else
  54. update(2 * v + 1, mid, right, pos, kek);
  55. }
  56. tree[v] = tree[2 * v] + tree[2 * v + 1];
  57.  
  58. }
  59.  
  60. int get_sum(int v, int left, int right, int r) {
  61. if (0 <= left && right <= r)
  62. return tree[v];
  63. if (right <= 0 || r <= left)
  64. return 0;
  65. int mid = (left + right) / 2;
  66. return get_sum(2 * v, left, mid,r) + get_sum(2 * v + 1, mid, right,r);
  67. }
  68.  
  69. int get_place(int v, int left, int right, int k) {
  70. if (left + 1 == right)
  71. return left;
  72. int mid = (left + right) / 2;
  73. if (k > tree[2 * v])
  74. get_place(2 * v, left, mid,k);
  75. else
  76. get_place(2 * v + 1, mid , right, k - tree[2 * v]);
  77. }
  78.  
  79.  
  80. void solve() {
  81. cin >> siz;
  82. for (int i = 0; i < siz; i++) {
  83. cin >> q;
  84. if (q > 0) {
  85. cout << get_place(1, 0, n, get_sum(1, 0, n, q)) << "\n";
  86. update(1, 0, n, get_sum(1, 0, n, q ), 0);
  87. }
  88. else
  89. update(1, 0, n, q + 1, 1);
  90. }
  91. }
  92.  
  93.  
  94. unsigned main() {
  95. //freopen("rvq.in", "r", stdin);
  96. //freopen("rvq.out", "w", stdout);
  97.  
  98. IOS;
  99. build(1,0,n);
  100. solve();
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement