fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. #define MAXNUM 100003
  4. #define MAXN 50003
  5. #define BUCKET_SIZE 230
  6. using namespace std;
  7. int n, m, k;
  8. int tr[MAXNUM];
  9. int get(int pos)
  10. {
  11.     if (pos <= 0)
  12.         return 0;
  13.         if (pos > 100000)
  14.             pos = 100000;
  15.     int ans = 0;
  16.     for (pos; pos >= 1; pos -= pos & -pos)
  17.         ans += tr[pos];
  18.     return ans;
  19. }
  20. void update(int pos, int add)
  21. {
  22.     for (pos; pos <= 100000; pos += pos & -pos)
  23.         tr[pos] += add;
  24. }
  25. struct query
  26. {
  27.     int l, r, idx;
  28.     bool operator < (const query &t) const
  29.     {
  30.         return ((l / BUCKET_SIZE < t.l / BUCKET_SIZE) || (l / BUCKET_SIZE == t.l / BUCKET_SIZE && r < t.r));
  31.     }
  32.     query() {}
  33.     query(int _l, int _r, int _idx)
  34.     {
  35.         l = _l;
  36.         r = _r;
  37.         idx = _idx;
  38.     }
  39. };
  40. int arr[MAXN];
  41. query queries[MAXN];
  42. int ans[MAXN];
  43. int cnt;
  44. void add_number(int num)
  45. {
  46.     cnt += get(num - k) + get(100000) - get(num + k - 1);
  47.     update(num, 1);
  48. }
  49. void extract_number(int num)
  50. {
  51.     cnt -= get(num - k) + get(100000) - get(num + k - 1);
  52.     update(num, -1);
  53. }
  54. void read()
  55. {
  56.     cin >> n >> m >> k;
  57.     for (int i = 1; i <= n; i++)
  58.         cin >> arr[i];
  59.     for (int i = 1; i <= m; i++)
  60.     {
  61.         cin >> queries[i].l >> queries[i].r;
  62.         queries[i].idx = i;
  63.     }
  64. }
  65. void solve()
  66. {
  67.     sort (queries+1, queries+m+1);
  68.     int l = queries[1].l, r = queries[1].r;
  69.     for (int i = l; i <= r; i++)
  70.         add_number(arr[i]);
  71.     ans[queries[1].idx] = cnt;
  72.     for (int i = 2; i <= m; i++)
  73.     {
  74.          while (l > queries[i].l)
  75.          {
  76.              l--;
  77.              add_number(arr[l]);
  78.          }
  79.          while (l < queries[i].l)
  80.          {
  81.              extract_number(arr[l]);
  82.              l++;
  83.          }
  84.          while (r > queries[i].r)
  85.          {
  86.              extract_number(arr[r]);
  87.              r--;
  88.          }
  89.          while (r < queries[i].r)
  90.          {
  91.              r++;
  92.              add_number(arr[r]);
  93.          }
  94.          ans[queries[i].idx] = cnt;
  95.     }
  96.     for (int i = 1; i <= m; i++)
  97.         cout << ans[i] << endl;
  98. }
  99. int main()
  100. {
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(nullptr);
  103.     cout.tie(nullptr);
  104.     read();
  105.     solve();
  106. }
  107. /*
  108. 5 5 2
  109. 1 2 3 4 5
  110. 1 3
  111. 2 4
  112. 3 5
  113. 1 5
  114. 2 5
  115. */
  116.  
Time limit exceeded #stdin #stdout 5s 16608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/SixJJL
problem CPAIR2, based on SPOJ submission 23314440 (CPP14), 2019-02-28 11:17:34
language:
C++14 (gcc 8.3)
created:
5 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!