fork(1) download
copy 
  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
comments (?)
stdin
copy 
5000000 2 6
1
2
3
5
10
5
stdout
copy 
0
1
2500001
3750001
5
3750001
stderr
copy 
time = 0.477s
https://ideone.com/FQiCvG
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!