fork download 
  1. /////////////////////////   _LeMur_
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #include <unordered_map>
  4. #include <unordered_set>
  5. #include <functional>
  6. #include <algorithm>
  7. #include <iostream>
  8. #include <cstring>
  9. #include <cassert>
  10. #include <chrono>
  11. #include <random>
  12. #include <bitset>
  13. #include <cstdio>
  14. #include <vector>
  15. #include <string>
  16. #include <ctime>
  17. #include <stack>
  18. #include <queue>
  19. #include <cmath>
  20. #include <ctime>
  21. #include <list>
  22. #include <map>
  23. #include <set>
  24.  
  25. using namespace std;
  26.  
  27. const int N = 100005;
  28. const int inf = 1000 * 1000 * 1000;
  29. const int mod = 1000 * 1000 * 1000 + 7;
  30.  
  31. int t;
  32. int n , k;
  33.  
  34. long long answ;
  35. int a[N] , b[N];
  36.  
  37. int mx1[N] , mx2[N];
  38.  
  39. void solve(int s,int e){
  40.     if(s == e){
  41.         if(abs(a[s] - b[s]) <= k){
  42.             ++answ;
  43.         }
  44.         return ;
  45.     }
  46.     ///
  47.     int m = (s + e) / 2;
  48.     solve(s , m);
  49.     solve(m + 1 , e);
  50.     ///
  51.     for(int step = 0; step < 2; step++){
  52.         for(int j=m+1;j<=e;j++){
  53.             mx1[j] = (j == m + 1) ? a[j] : max(mx1[j - 1] , a[j]);
  54.             mx2[j] = (j == m + 1) ? b[j] : max(mx2[j - 1] , b[j]);
  55.         }
  56.         int m1 , m2;
  57.         for(int i=m;i>=s;i--){
  58.             m1 = (i == m) ? a[i] : max(m1 , a[i]);
  59.             m2 = (i == m) ? b[i] : max(m2 , b[i]);
  60.             int id1 , id2;
  61.             if(step == 1)
  62.                 id1 = lower_bound(mx1 + m + 1 , mx1 + e + 1 , m1) - mx1;
  63.             else
  64.                 id1 = upper_bound(mx1 + m + 1 , mx1 + e + 1 , m1) - mx1;
  65.             id2 = upper_bound(mx2 + m + 1 , mx2 + e + 1 , m2) - mx2;
  66.             ///
  67.             if(abs(m1 - m2) <= k)
  68.                 answ += max(0 , min(id1 , id2) - (m + 1));
  69.             ///
  70.             int id3 = lower_bound(mx2 + id2 , mx2 + e + 1 , m1 - k) - mx2;
  71.             int id4 = upper_bound(mx2 + id2 , mx2 + e + 1 , m1 + k) - mx2;
  72.             answ += max( min(id1 , id4) - id3 , 0);
  73.         }
  74.         ///
  75.         reverse(a + s , a + e + 1);
  76.         reverse(b + s , b + e + 1);
  77.         m = e - m + s - 1;
  78.     }
  79. }
  80.  
  81. int main() {
  82.     cin >> t;
  83.     int test = 0;
  84.     while(t--){
  85.         ++test;
  86.         answ = 0;
  87.         scanf("%d%d",&n,&k);
  88.         for(int i=1;i<=n;i++){
  89.             scanf("%d",&a[i]);
  90.         }
  91.         for(int i=1;i<=n;i++){
  92.             scanf("%d",&b[i]);
  93.         }
  94.         solve(1 , n);
  95.         printf("Case #%d: %lld\n",test,answ);
  96.     }
  97. 	return 0;
  98. }
  99.  
Success #stdin #stdout 0s 16800KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/oxJUh9
language:
C++ 4.3.2 (gcc-4.3.2)
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!