fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef unsigned long long  ull;
  6.  
  7. #define     mem(a,b)        memset(a,b,sizeof(a))
  8. #define     mp              make_pair
  9. #define     pii             pair<int,int>
  10. #define     fs              first
  11. #define     sc              second
  12. #define     VI              vector<int>
  13. #define     clr(a)          a.clear()
  14. #define     pob             pop_back
  15. #define     pub             push_back
  16. #define     eps             1E-5
  17. #define     sf              scanf
  18. #define     pf              printf
  19. #define     all(a)          a.begin(),a.end()
  20. #define     allr(a)         a.rbegin(),a.rend()
  21. #define     full(a,l)       a,a+l
  22. #define     fread(name)     freopen(name,"r",stdin)
  23. #define     fwrite(name)    freopen(name,"w",stdout)
  24. #define     sz(a)           a.size()
  25. #define     count_one       __builtin_popcount
  26. #define     count_onell     __builtin_popcountll
  27. #define     fastIO          ios_base::sync_with_stdio(false)
  28. #define     PI              (acos(-1.0))
  29. #define     linf            (1LL<<62)//>4e18
  30. #define     inf             (0x7f7f7f7f)//>2e9
  31. #define     fore(x,i)       for(typeof((x).begin()) i=(x.begin()); i!=(x).end(); ++i)
  32. #define     rfore(x,i)      for(typeof((x).rbegin()) i=(x.rbegin()); i!=(x).rend(); ++i)
  33. #define     For(i,a,b)      for(int i=a;i<=b;++i)
  34. #define     rFor(i,a,b)     for(int i=a;i>=b;--i)
  35.  
  36. template<class T> T pwr(T b, T p)
  37. {
  38.     T r=1,x=b;
  39.     while(p)
  40.     {
  41.         if(p&1)r*=x;
  42.         x*=x;
  43.         p=(p>>1);
  44.     }
  45.     return r;
  46. }
  47. template<class T> T lcm(T a,T b)
  48. {
  49.     return(a/__gcd(a,b))*b;
  50. }
  51. template<class T> T sqr(T a)
  52. {
  53.     return a*a;
  54. }
  55. template<class T> void xswap (T &x,T &y)
  56. {
  57.     if(x!=y)
  58.     {
  59.         x^=y;
  60.         y^=x;
  61.         x^=y;
  62.     }
  63. }
  64. template<typename T> inline bool isOn(T &mask,int pos)
  65. {
  66.     return((mask)&(1LL<<pos));
  67. }
  68. template<typename T> inline T setf(T mask,int pos)
  69. {
  70.     return mask=((mask)&(~(1LL<<pos)));
  71. }
  72. template<typename T> inline T sett(T mask,int pos)
  73. {
  74.     return mask=((mask)(1LL<<pos));
  75. }
  76. template<typename T> inline T flip(T mask,int pos)
  77. {
  78.     return mask=((mask)^(1LL<<pos));
  79. }
  80.  
  81. template<class T> string to_string(T n)
  82. {
  83.     ostringstream oss;
  84.     oss<<n;
  85.     oss.flush();
  86.     return oss.str();
  87. }
  88. int to_int(string s)
  89. {
  90.     int r=0;
  91.     istringstream sin(s);
  92.     sin>>r;
  93.     return r;
  94. }
  95.  
  96. template<class T1> void put(T1 e)
  97. {
  98.     cout<<e<<endl;
  99. }
  100. template<class T1,class T2> void put(T1 e1,T2 e2)
  101. {
  102.     cout<<e1<<" "<<e2<<endl;
  103. }
  104. template<class T1,class T2,class T3> void put(T1 e1,T2 e2,T3 e3)
  105. {
  106.     cout<<e1<<" "<<e2<<" "<<e3<<endl;
  107. }
  108. template<class T1,class T2,class T3,class T4> void put(T1 e1,T2 e2,T3 e3,T4 e4)
  109. {
  110.     cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<endl;
  111. }
  112. template<class T1,class T2,class T3,class T4,class T5> void put(T1 e1,T2 e2,T3 e3,T4 e4,T5 e5)
  113. {
  114.     cout<<e1<<" "<<e2<<" "<<e3<<" "<<e4<<" "<<e5<<endl;
  115. }
  116. template<class T1> void putv(vector<T1>e1)
  117. {
  118.     for(int i=0; i<sz(e1); i++)(!i?cout<<e1[i]:cout<<" "<<e1[i]);
  119.     cout<<endl;
  120. }
  121. template<class T1> void puta(T1 arr[],int l)
  122. {
  123.     for(int i=0; i<l; i++)(!i?cout<<arr[i]:cout<<" "<<arr[i]);
  124.     cout<<endl;
  125. }
  126. template<class T1> bool tk(T1 &e1)
  127. {
  128.     return(cin>>e1?true:false);
  129. }
  130. template<class T1,class T2> bool tk(T1 &e1,T2 &e2)
  131. {
  132.     return(cin>>e1>>e2?true:false);
  133. }
  134. template<class T1,class T2,class T3> bool tk(T1 &e1,T2 &e2,T3 &e3)
  135. {
  136.     return(cin>>e1>>e2>>e3?true:false);
  137. }
  138. template<class T1,class T2,class T3,class T4> bool tk(T1 &e1,T2 &e2,T3 &e3,T4 &e4)
  139. {
  140.     return(cin>>e1>>e2>>e3>>e4?true:false);
  141. }
  142.  
  143. #define mx 100001
  144. int arr[mx];
  145. int tree[mx*3];
  146. //int t1[mx*3];
  147.  
  148. void init( int node,int b,int e )
  149. {
  150.     if( b==e )
  151.     {
  152.         tree[node]=arr[b];
  153.         return ;
  154.     }
  155.     int Left=node*2;
  156.     int Right=Left+1;
  157.     int mid=(b+e)/2;
  158.     init( Left,b,mid );
  159.     init( Right,mid+1,e );
  160.     tree[node]=min( tree[Left],tree[Right] );
  161.  
  162. }
  163.  
  164. int query( int node,int b,int e,int i,int j )
  165. {
  166.     if( j<b || i>e ) return 0;
  167.     if( i<=b && e<=j )
  168.     {
  169.         return tree[node];
  170.     }
  171.  
  172.     int Left  = node*2;
  173.     int Right = Left+1;
  174.     int mid   = (b+e)/2;
  175.     int q1    = query(  Left,      b, mid, i, j );
  176.     int q2    = query( Right,  mid+1,   e, i, j );
  177.     int m     = min( q1,q2 );
  178.     if( m==0 )
  179.     {
  180.     	m=max(q1,q2);
  181.     	if( m==0 )
  182.         m=mx;
  183.     }
  184.     return m;
  185. }
  186.  
  187. int main()
  188. {
  189.  
  190. //freopen("in.txt","r",stdin );
  191. //freopen("out.txt","w",stdout );
  192.     int n,i,j,q,t,b,e,r=0;
  193.     sf("%d",&t);
  194.     for( i=1; i<=t; i++ )
  195.     {
  196.         sf("%d %d",&n,&q);
  197.         for( j=1; j<=n; j++ )
  198.         {
  199.             sf("%d",&arr[j]);
  200.         }
  201.  
  202.         init(1,1,n);
  203.  
  204.         pf("Case %d:\n",i);
  205.  
  206.         for( j=1; j<=q; j++ )
  207.         {
  208.             sf("%d %d",&b,&e);
  209.             r=query(1,1,n,b,e);
  210.             if( r==mx )
  211.             r=0;
  212.             pf("%d\n",r);
  213.         }
  214.     }
  215.     return 0;
  216. }
Success #stdin #stdout 0s 4708KB
comments (?)
stdin
copy 
1
5 3
0 0 0 0 0
1
1 2
1 3
3 5
stdout
copy 
Case 1:
0
0
0
https://ideone.com/xiwiFE
language:
C++14 (gcc 8.3)
created:
9 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!