fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define MAX 1000000000000000000
  5.  
  6. ll segtree[400005];
  7. ll lazy[400005];
  8. ll arr[100005];
  9.  
  10. void build(ll n,ll b,ll e){
  11.     if(b>e){
  12.         return;
  13.     }
  14.  
  15.     if(b==e){
  16.         segtree[n]=arr[b];
  17.         return;
  18.     }
  19.  
  20.     ll mid=(b+e)/2;
  21.     build(2*n+1,b,mid);
  22.     build(2*n+2,mid+1,e);
  23.  
  24.     segtree[n]=min(segtree[2*n+1],segtree[2*n+2]);
  25. }
  26.  
  27. void update(ll n,ll b,ll e,ll l,ll r,ll value)
  28. {
  29.  
  30.     if(b>e){
  31.         return;
  32.     }
  33.  
  34.     if(lazy[n]!=0){
  35.         segtree[n]+=lazy[n];
  36.             if(b!=e){
  37.             lazy[2*n+1]+=lazy[n];
  38.             lazy[2*n+2]+=lazy[n];
  39.             }
  40.         lazy[n]=0;
  41.     }
  42.  
  43.     if(b>r||e<l){
  44.         return;
  45.     }
  46.  
  47.     if(l<=b&&r>=e){
  48.         segtree[n]+=value;
  49.             if(b!=e)
  50.             {
  51.                 lazy[2*n+1]+=value;
  52.                 lazy[2*n+2]+=value;
  53.             }
  54.         return;
  55.     }
  56.  
  57.     ll mid=(b+e)/2;
  58.     update(2*n+1,b,mid,l,r,value);
  59.     update(2*n+2,mid+1,e,l,r,value);
  60.  
  61.     segtree[n]=min(segtree[2*n+1],segtree[2*n+2]);
  62.  
  63. }
  64.  
  65.  
  66. ll query(ll n,ll b,ll e,ll l,ll r){
  67.  
  68.     if(b>e){
  69.             return MAX;
  70.     }
  71.  
  72.     if(lazy[n]!=0){
  73.         segtree[n]+=lazy[n];
  74.             if(b!=e){
  75.                 lazy[2*n+1]+=lazy[n];
  76.                 lazy[2*n+2]+=lazy[n];
  77.             }
  78.         lazy[n]=0;
  79.     }
  80.  
  81.  
  82.     if(b>r||e<l){
  83.         return MAX;
  84.     }
  85.  
  86.     if(l<=b&&r>=e){
  87.         return segtree[n];
  88.     }
  89.  
  90.     ll mid=(b+e)/2;
  91.  
  92.     return min(query(2*n+1,b,mid,l,r),query(2*n+2,mid+1,e,l,r));
  93. }
  94.  
  95. int main()
  96. {
  97.         ll i,j,n,m,t,a,b,value,q,c;
  98.  
  99.         scanf("%lld",&n);
  100.  
  101.         for(i=1;i<=n;i++){
  102.             scanf("%lld",&arr[i]);
  103.         }
  104.  
  105.         build(1,1,n);
  106.  
  107.         scanf("%lld",&q);
  108.         for(i=0;i<q;i++){
  109.             scanf("%lld%lld%lld",&a,&b,&c);
  110.             if(a==1){
  111.                 scanf("%lld",&value);
  112.                 update(1,1,n,b,c,value);
  113.             }
  114.             else{
  115.                 printf("%lld\n",query(1,1,n,b,c));
  116.             }
  117.         }
  118. }
  119.  
Time limit exceeded #stdin #stdout 5s 4288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/S6yxAe
language:
C++14 (gcc 8.3)
created:
4 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!