fork download
copy 
  1. #include<unordered_map>
  2. #include<unordered_set>
  3. #include<functional>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<hash_map>
  7. #include<iterator>
  8. #include<iomanip>
  9. #include<numeric>
  10. #include<cstring>
  11. #include<vector>
  12. #include<string>
  13. #include<deque>
  14. #include<stack>
  15. #include<queue>
  16. #include<array>
  17. #include<cmath>
  18. #include<list>
  19. #include<map>
  20. #include<set>
  21. using namespace std;
  22. typedef long long ll;
  23. typedef unsigned long long ull;
  24. typedef double db;
  25. #define pii pair<int,int>
  26. #define pll pair<ll,ll>
  27. #define inf INT32_MAX
  28. #define linf INT64_MAX
  29. #define pf push_front
  30. #define pb push_back
  31. #define ppb pop_back
  32. #define ppf pop_front
  33. #define ff first
  34. #define ss second
  35. const int mod=1e9+7,N=5e4+5,logN=18;
  36. ll Pow(ll b,ll p){
  37.     if(!p)return 1;
  38.     if(p==1)return b;
  39.     ll tmp=Pow(b,p/2);
  40.     tmp=(tmp*tmp);
  41.     if(p&1)tmp=(tmp*b);
  42.     return tmp;
  43. }
  44. int n,q,a[N],st[N][logN],Log[N],ans;
  45.  
  46. void calcLog(){
  47.     Log[1]=0;
  48.     for(int i=2;i<N;++i)Log[i]=Log[i/2]+1;
  49. }
  50.  
  51. void preComp(){
  52.     for(int i=0;i<n;++i)st[i][0]=a[i];
  53.  
  54.     for(int i=1;i<=Log[n];++i){
  55.         for(int j=0;j+(1<<i)-1<n;++j){
  56.             st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
  57.         }
  58.     }
  59. }
  60.  
  61. int qAnswer(int l,int r){
  62.     int length=r-l+1;
  63.     return max(st[l][Log[length]],st[r-(1<<Log[length])+1][Log[length]]);
  64. }
  65.  
  66. bool solve(){
  67.     cin>>n>>q;
  68.     for(int i=0;i<n;++i)cin>>a[i];
  69.     calcLog();
  70.     preComp();
  71.     for(int i=0;i<q;++i){
  72.         int l,r;
  73.         cin>>l>>r;
  74.         l--,r--;
  75.         if((r-l-1)>0){
  76.             if(a[l]>=qAnswer(l+1,r-1))ans++;
  77.         }
  78.         else ans++;
  79.     }
  80.     cout<<ans;
  81. }
  82. int main(){
  83.     ios_base::sync_with_stdio(false);
  84.     cin.tie(nullptr);
  85.     int t=1;
  86.     //cin>>t;
  87.     while(t--){
  88.         solve();
  89.     }
  90. }
Runtime error #stdin #stdout 0s 5696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HBFP8t
problem THRBL, based on SPOJ submission 28279633 (CPP14), 2021-08-03 21:56:55
language:
C++14 (gcc 8.3)
created:
2 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!