fork download 
  1. //"Never be ashamed of where you are when you start. Skyscrapers are built from the ground up."
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. using ll = long long;
  5. using db = long double;
  6. using str = string;
  7. using pii = pair<int, int>;
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define lb lower_bound
  12. #define ub upper_bound
  13. #define all(x) (x).begin(), (x).end()
  14. #define nl cout << '\n';
  15. #define itn int
  16. #define pi acos(-1.0)
  17. #define task ""
  18.  
  19. /** Optimization **/
  20. void fastIO(){
  21.     ios_base::sync_with_stdio(false);
  22.     cin.tie(NULL);
  23.     cout.tie(NULL);
  24.     if (fopen(task".INP", "r")){
  25.         freopen(task".INP", "r", stdin);
  26.         freopen(task".OUT", "w", stdout);
  27.     }
  28. }
  29.  
  30. /** Variables **/
  31. const ll INF = 1e18+1;
  32. const ll MOD = 998244353; //1e9+7;
  33. int n, m, x, y;
  34. int a[50005], b[50005], sta[17][50005], stb[17][50005];
  35.  
  36. /** Functions **/
  37.  
  38.  
  39. /** Main code **/
  40. void RPMCPP(){
  41.     int i, j, k, res;
  42.     cin >> n >> m;
  43.     for (i = 1; i <= n; i++){
  44.         cin >> a[i];
  45.         b[n-i+1] = a[i];
  46.     }
  47.     for (i = 1; i <= n; i++){
  48.         sta[0][i] = a[i];
  49.         stb[0][i] = b[i];
  50.     }
  51.     for (i = 1; i <= 16; i++){
  52.         for (j = 1; j+(1<<i)-1 <= n; j++){
  53.             sta[i][j] = max(sta[i-1][j], sta[i-1][j+(1<<(i-1))]);
  54.             stb[i][j] = max(stb[i-1][j], stb[i-1][j+(1<<(i-1))]);
  55.         }
  56.     }
  57.     res = 0;
  58.     while (m--){
  59.         cin >> x >> y;
  60.         if (x <= y){
  61.             y--;
  62.             k = __lg(y-x+1);
  63.             if (a[x] == max(sta[k][x], sta[k][y-(1<<k)+1])){
  64.                 res++;
  65.             }
  66.         } else {
  67.             x--;
  68.             swap(x, y);
  69.             k = __lg(y-x+1);
  70.             if (b[x] == max(stb[k][x], stb[k][y-(1<<k)+1])){
  71.                 res++;
  72.             }
  73.         }
  74.     }
  75.     cout << res;
  76. }
  77.  
  78. signed main(){
  79.     fastIO();
  80.     RPMCPP();
  81. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/YCyeix
problem THRBL, based on SPOJ submission 33017753 (CPP14), 2024-05-07 17:54:48
language:
C++14 (gcc 8.3)
created:
11 days 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!