fork download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  6.  
  7.  
  8. class SqrtDecomposition {
  9.  
  10.     int size, blockSize, blocksCount;
  11.     vector<int> array;
  12.     vector< vector<int> > blocks;
  13.  
  14. public:
  15.  
  16.     SqrtDecomposition(const vector<int> &a) {
  17.         array = a;
  18.         size = a.size();
  19.         blockSize = sqrt(size);
  20.         blocksCount = size / blockSize + (size % blockSize ? 1 : 0);
  21.         blocks.resize(blocksCount);
  22.         for (int i = 0; i < size; i++)
  23.             blocks[i / blockSize].push_back(a[i]);
  24.         for (int i = 0; i < blocksCount; i++)
  25.             sort(blocks[i].begin(), blocks[i].end());
  26.     }
  27.  
  28.     int query(int l, int r, int k) const {
  29.         int res = 0;
  30.         while (l <= r && l % blockSize != 0)
  31.             res += array[l++] > k;
  32.         while (l <= r && r % blockSize != blockSize - 1)
  33.             res += array[r--] > k;
  34.         if (l <= r)
  35.             for (l /= blockSize, r /= blockSize; l <= r; l++)
  36.                 res += blocks[l].end() - upper_bound(blocks[l].begin(), blocks[l].end(), k);
  37.         return res;
  38.     }
  39.  
  40. };
  41.  
  42.  
  43. int main() {
  44.     int aSize;
  45.     scanf("%d", &aSize);
  46.  
  47.     vector<int> a(aSize);
  48.     for (int i = 0; i < aSize; i++)
  49.         scanf("%d", &a[i]);
  50.  
  51.     SqrtDecomposition sd(a);
  52.  
  53.     int queriesCount;
  54.     scanf("%d", &queriesCount);
  55.  
  56.     for (int i = 0; i < queriesCount; i++) {
  57.         int l, r, k;
  58.         scanf("%d%d%d", &l, &r, &k);
  59.         printf("%d\n", sd.query(l - 1, r - 1, k));
  60.     }
  61. }
Success #stdin #stdout 0s 3480KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
stdout
copy 
2
0
3
https://ideone.com/qXTfr3
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

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!