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