fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define pb push_back
  8. #define pii pair<int, int>
  9. #define ff first
  10. #define ss second
  11. #define nl '\n'
  12. #define mod 1000000007
  13. #define inf 1000000009
  14. #define MAXX 1000000000000015
  15. #define LIM 300005
  16. #define eps 1e-9
  17. #define pi acos(-1)
  18.  
  19. using namespace std;
  20. using namespace __gnu_pbds;
  21.  
  22. #define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag, tree_order_statistics_node_update>
  23.  
  24. void FAST_IO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
  25.  
  26. int arr[LIM];
  27. int minTable[LIM][22], maxTable[LIM][22], logArray[LIM];
  28.  
  29. void construct(int n)
  30. {
  31.     logArray[1] = 0;
  32.     for(int i = 2; i <= n; i++)
  33.         logArray[i] = 1 + logArray[i/2];
  34.  
  35.     for(int i = 0; i < n; i++){
  36.         minTable[i][0] = arr[i];
  37.         maxTable[i][0] = arr[i];
  38.     }
  39.  
  40.     for(int j = 1; j <= logArray[n] + 1; j++){
  41.         for(int i = 0; i + (1 << (j - 1)) < n; i++){
  42.             minTable[i][j] = min(minTable[i][j - 1], minTable[i + (1 << (j - 1)) ][j - 1]);
  43.             maxTable[i][j] = max(maxTable[i][j - 1], maxTable[i + (1 << (j - 1)) ][j - 1]);
  44.         }
  45.     }
  46. }
  47.  
  48. int minQuery(int L, int R)
  49. {
  50.     int len = R - L + 1;
  51.     int lg = logArray[len];
  52.     return min(minTable[L][lg], minTable[R - (1 << lg) + 1][lg]);
  53. }
  54.  
  55. int maxQuery(int L, int R)
  56. {
  57.     int len = R - L + 1;
  58.     int lg = logArray[len];
  59.     return max(maxTable[L][lg], maxTable[R - (1 << lg) + 1][lg]);
  60. }
  61.  
  62. int bs(int pos, int n, int x, int y)
  63. {
  64.     int lo = pos, hi = n - 1, md, ans = pos - 1;
  65.     while(lo <= hi){
  66.         md = lo + (hi - lo)/2;
  67.         int rangeMin = minQuery(pos, md);
  68.         int rangeMax = maxQuery(pos, md);
  69.         if(x == rangeMax && rangeMin == y){
  70.             ans = md;
  71.             lo = md + 1;
  72.         }
  73.         else if((x >= rangeMax && y < rangeMin) || (x > rangeMax && y <= rangeMin)){
  74.             lo = md + 1;
  75.         }
  76.         else{
  77.             hi = md - 1;
  78.         }
  79.     }
  80.     return ans;
  81. }
  82.  
  83. int bs2(int pos, int n, int x, int y)
  84. {
  85.     int lo = pos, hi = n - 1, md, ans = pos;
  86.     while(lo <= hi){
  87.         md = lo + (hi - lo)/2;
  88.         int rangeMin = minQuery(pos, md);
  89.         int rangeMax = maxQuery(pos, md);
  90.         if(x == rangeMax && rangeMin == y){
  91.             ans = md;
  92.             hi = md - 1;
  93.         }
  94.         else if((x >= rangeMax && y < rangeMin) || (x > rangeMax && y <= rangeMin)){
  95.             lo = md + 1;
  96.         }
  97.         else{
  98.             hi = md - 1;
  99.         }
  100.     }
  101.     return ans;
  102. }
  103.  
  104. int main()
  105. {
  106.     ///MUST READ THE POINTS BELOW BEFORE SUBMIT
  107.  
  108.     FAST_IO();
  109.  
  110.     int n, x, y;
  111.  
  112.     cin >> n >> x >> y;
  113.     for(int i = 0; i < n; i++)
  114.         cin >> arr[i];
  115.  
  116.     construct(n);
  117.  
  118.     ll ans = 0;
  119.     for(int i = 0; i < n; i++){
  120.         ans += bs(i, n, x, y) - bs2(i, n, x, y) + 1;
  121.     }
  122.  
  123.     cout << ans << nl;
  124.  
  125.     return 0;
  126.     ///MUST READ THE POINTS BELOW BEFORE SUBMIT
  127. }
  128. /**
  129.     1. LOOK SPECIAL CASE N = 1.
  130.     2. LOOK FOR OVERFLOW.
  131.     3. LOOK FOR OUT OF BOUNDS.
  132. **/
  133.  
Success #stdin #stdout 0.01s 5396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/HW0zYK
language:
C++14 (gcc 8.3)
created:
1 year 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!