fork download
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <cassert>
  6.  
  7. struct SegmentTree {
  8.  
  9. int size;
  10.  
  11. std::vector<int> data;
  12.  
  13. void build(int v, int l, int r, const std::vector<bool>& array) {
  14. if (l == r) {
  15. data[v] = array[l];
  16. } else {
  17. int m = (l + r) / 2;
  18. build(2*v+1, l, m, array);
  19. build(2*v+2, m+1, r, array);
  20. data[v] = data[2*v+1] + data[2*v+2];
  21. }
  22. }
  23.  
  24. void set(int v, int l, int r, int p, int a) {
  25. if (l == r) {
  26. data[v] = a;
  27. } else {
  28. int m = (l + r) / 2;
  29. if (p <= m) {
  30. set(2*v+1, l, m, p, a);
  31. } else {
  32. set(2*v+2, m+1, r, p, a);
  33. }
  34. data[v] = data[2*v+1] + data[2*v+2];
  35. }
  36. }
  37.  
  38. void set(int pos, int value) {
  39. set(0, 0, size-1, pos, value);
  40. }
  41.  
  42. int get(int sum) const {
  43. // Найти самый левый r, такой что сумма на отрезке [0, r] равна sum.
  44. int v = 0, l = 0, r = size-1;
  45. while (l < r) {
  46. if (data[2*v+1] >= sum) {
  47. v = 2*v+1;
  48. r = (l+r) / 2;
  49. } else {
  50. sum -= data[2*v+1];
  51. v = 2*v+2;
  52. l = (l+r) / 2 + 1;
  53. }
  54. }
  55. return r;
  56. }
  57.  
  58. SegmentTree(const std::vector<bool>& array) {
  59. size = (int)array.size();
  60. int pow = 1;
  61. while (pow < size) pow *= 2;
  62. assert(pow >= size);
  63. data.resize(2*pow);
  64. build(0, 0, size-1, array);
  65. }
  66. };
  67.  
  68. int main() {
  69. double t = clock();
  70.  
  71. int n, k, q;
  72. scanf("%d %d %d", &n, &k, &q);
  73.  
  74. std::vector<int> answer(1+n, 0);
  75.  
  76. SegmentTree st(std::vector<bool>(1+n,true));
  77.  
  78. st.set(0,0);
  79.  
  80. while (n >= k) {
  81. int sum = k, erased = 0, limit = n / k;
  82. while (erased < limit) {
  83. int number = st.get(sum);
  84. st.set(number, 0);
  85. answer[number] = (int)answer.size() - n + erased;
  86. sum += k - 1;
  87. ++erased;
  88. }
  89. n -= erased;
  90. }
  91.  
  92. while (q--) {
  93. int item;
  94. scanf("%d", &item);
  95. printf("%d\n", answer[item]);
  96. }
  97. fprintf(stderr, "time = %0.3fs\n", (clock() - t) / CLOCKS_PER_SEC);
  98. return 0;
  99. }
Success #stdin #stdout #stderr 0.78s 87984KB
stdin
5000000 2 6
1
2
3
5
10
5
stdout
0
1
2500001
3750001
5
3750001
stderr
time = 0.780s