fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll=long long;
  5. //using int=long long;
  6. int const MAXN=1e5+10;
  7. int const INF=2e9+10;
  8. void open(){
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL); cout.tie(NULL);
  11. //    freopen(TASK".INP","r",stdin);
  12. //    freopen(TASK".OUT","w",stdout);
  13. }
  14. pair<int,int> f[MAXN];
  15. pair<pair<int,int>,int> s[MAXN];
  16. bool ans[MAXN];
  17. int N,B;
  18.  
  19. int main() {
  20.     open();
  21.     cin>>N>>B;
  22.     for(int i=1;i<=N;i++){
  23.         cin>>f[i].first;
  24.         f[i].second=i;
  25.     }
  26.  
  27.     for(int i=1;i<=B;i++){
  28.         cin>>s[i].first.first>>s[i].first.second;
  29.         s[i].second=i;
  30.     }
  31.  
  32.     sort(f+1,f+N+1);
  33.     sort(s+1,s+B+1);
  34.  
  35.     set<int> points;
  36.     multiset<int> dist;
  37.     points.insert(1);points.insert(N);dist.insert(N-1);
  38.  
  39.     for(int i=1,j=0;i<=B;i++){
  40.         while(j<N && f[j+1].first<=s[i].first.first){
  41.             j++;
  42.             auto right=points.upper_bound(f[j].second);
  43.             auto left=prev(right);
  44.  
  45.             dist.erase(dist.find(*right-*left));
  46.             dist.insert(f[j].second-*left);
  47.             dist.insert(*right-f[j].second);
  48.             points.insert(f[j].second);
  49.         }
  50.         bool flag=0;
  51.         int max_dist=*dist.rbegin();
  52.  
  53.         if(max_dist<=s[i].first.second) flag=1;
  54.         ans[s[i].second]=flag;
  55.     }
  56.  
  57.     for(int i=1;i<=B;i++){
  58.         cout<<ans[i]<<"\n";
  59.     }
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/6duI0X
language:
C++ (gcc 8.3)
created:
10 hours 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!