fork download
copy 
  1. //include <zadr>
  2. /*
  3.     name : SHOKEY BAURZHAN ||
  4.     school : AKTOBE BIL ||
  5.     medal : IOI GOLDE INSH ||
  6.     second name : ZADR ||
  7.     handl : BR9VERnd ||
  8. */
  9.  
  10.  
  11. #include <bits/stdc++.h>
  12.  
  13. //BR9VERnd
  14. //IOI GOLD insh
  15.  
  16. using namespace std;
  17.  
  18. #define ll long long
  19. #define all(v)  v.begin(), v.end()
  20. #define pb push_back
  21. #define sz(a) (int)a.size()
  22. #define ld long double
  23. #define ull unsigned long long
  24. #define nd second
  25. #define st first
  26. #define bp __builtin_popcount
  27. #define pl __builtin_popcountl
  28. #define pll __builtin_popcountll
  29. #define up upper_bound
  30. #define lw lower_bound
  31.  
  32.  
  33. const int N=2e5+5;
  34. const string alp="abcdefghijklmnopqrstuvwxyz";
  35.  
  36. int n,q,k,a[N],b[500],d,z[500];
  37. void push(int bl){
  38.     if(!z[bl])return;
  39.     for(int i=bl*d;i<(bl+1)*d;i++)
  40.         a[i]+=z[bl];
  41.     z[bl]=0;
  42. }
  43. bool check(int l,int r){
  44.     int m=0;
  45.     int bl=l/d;
  46.     int br=r/d;
  47.  
  48.     if(br==bl){
  49.         push(bl);
  50.         for(int i=l;i<=r;i++){
  51.             m=max(m,a[i]);
  52.         }
  53.     }
  54.     else{
  55.         push(bl);
  56.         push(br);
  57.         for(int i=l;i<(bl+1)*d;i++)
  58.             m=max(m,a[i]);
  59.         for(int i=bl+1;i<br;i++)
  60.             m=max(m,b[i]);
  61.         for(int i=br*d;i<=r;i++)
  62.             m=max(m,a[i]);
  63.     }
  64.     if(m==k)return 0;
  65.     if(br==bl){
  66.         for(int i=l;i<=r;i++){
  67.             a[i]++;
  68.             b[bl]=max(b[bl],a[i]);
  69.         }
  70.     }
  71.     else{
  72.         for(int i=l;i<(bl+1)*d;i++){
  73.             a[i]++;
  74.             b[bl]=max(b[bl],a[i]);
  75.         }
  76.         for(int i=bl+1;i<br;i++){
  77.             z[i]++;
  78.             b[i]++;
  79.         }
  80.         for(int i=br*d;i<=r;i++){
  81.             a[i]++;
  82.             b[br]=max(a[i],b[br]);
  83.         }
  84.     }
  85.  
  86.  
  87.     return 1;
  88. }
  89.  
  90. int main(){
  91.     ios_base::sync_with_stdio(0);
  92.     cin.tie(0);
  93.  
  94.     cin>>n>>k>>q;
  95.     d=sqrt(n);
  96.     while(q--){
  97.         int l,r;
  98.         cin>>l>>r;
  99.         cout<<check(l,r-1)<<'\n';
  100.     }
  101.  
  102.  
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wh89Ld
language:
C++ (gcc 8.3)
created:
2 years 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!