Advertisement
Saleh127

Spoj Negative Score

Jun 12th, 2021
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.25 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. ll a[100005];
  6. ll tree[400005];
  7.  
  8. void treeconstruct(ll node,ll b,ll e)
  9. {
  10. if(b>=e)
  11. {
  12. if(b==e) tree[node]=a[b];
  13. return;
  14. }
  15.  
  16. ll left = node*2;
  17. ll right = node*2 + 1ll;
  18.  
  19. ll mid=(b+e)/2;
  20.  
  21. treeconstruct(left,b,mid);
  22. treeconstruct(right,mid+1,e);
  23.  
  24. tree[node]=min(tree[left],tree[right]);
  25.  
  26. }
  27.  
  28. ll queries(ll node,ll b,ll e,ll i,ll j)
  29. {
  30. if(i>e || j<b) return INT_MAX;
  31.  
  32. if(b>=i && e<=j) return tree[node];
  33. if(b>e) return INT_MAX;
  34.  
  35. ll left = node*2;
  36. ll right = node*2 + 1ll;
  37.  
  38. ll mid=(b+e)/2;
  39.  
  40. ll x=queries(left,b,mid,i,j);
  41.  
  42. ll y=queries(right,mid+1,e,i,j);
  43.  
  44. return min(x,y);
  45.  
  46. }
  47.  
  48. int main()
  49. {
  50. ios_base::sync_with_stdio(0);
  51. cin.tie(0);cout.tie(0);
  52.  
  53. test
  54. {
  55. ll q,n,m,i,j,k,l;
  56.  
  57. cin>>n>>q;
  58.  
  59. for(i=1;i<=n;i++) cin>>a[i];
  60.  
  61. cout<<"Scenario #"<<cs<<":"<<endl;
  62.  
  63. treeconstruct(1ll,1ll,n);
  64.  
  65. while(q--)
  66. {
  67. cin>>k>>l;
  68.  
  69. m=queries(1ll,1ll,n,k,l);
  70.  
  71. cout<<m<<endl;
  72. }
  73.  
  74.  
  75. }
  76.  
  77. return 0;
  78. }
  79.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement