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