fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll=long long;
  4. #define haimu(x) (1<<(x))
  5. #define nl '\n'
  6. int main () {
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     int n,q;
  10.     cin >> n >> q;
  11.     vector <int> a(n+1);
  12.     int k=log2(n)+1;
  13.     vector<vector<int>> st(n+1,vector<int>(k));
  14.     for (int i=1;i<=n;i++) {
  15.         cin >> a[i];
  16.         st[i][0]=a[i];
  17.     }
  18.     for (int j=1;(haimu (j))<=n;j++) {
  19.         for (int i=1;i+(haimu (j))-1<=n;i++) {
  20.             st[i][j]=max(st[i][j-1],st[i+(haimu (j-1))][j-1]);
  21.         }
  22.     }
  23.     int cnt=0;
  24.     while (q--) {
  25.         int l,r;
  26.         cin >> l >> r;
  27.         int k=floor(log2(r-l+1));
  28.         if (max(st[l][k],st[r-(haimu(k))+1][k])==a[l]) cnt++;
  29.     }
  30.     cout << cnt;
  31.     return 0;
  32. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
7 3
2 3 5 4 2 1 6
3 5
2 5
4 6
stdout
copy 
2
https://ideone.com/QjlLCF
language:
C++ (gcc 8.3)
created:
1 day 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!