結果

問題 No.1234 典型RMQ
ユーザー suzuken_wsuzuken_w
提出日時 2020-09-18 23:54:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,040 bytes
コンパイル時間 2,865 ms
コンパイル使用メモリ 215,828 KB
実行使用メモリ 8,192 KB
最終ジャッジ日時 2024-04-26 11:18:55
合計ジャッジ時間 6,915 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 112 ms
7,936 KB
testcase_07 AC 85 ms
5,376 KB
testcase_08 AC 122 ms
8,192 KB
testcase_09 AC 104 ms
5,632 KB
testcase_10 AC 120 ms
7,936 KB
testcase_11 AC 109 ms
7,808 KB
testcase_12 AC 98 ms
5,760 KB
testcase_13 AC 85 ms
5,376 KB
testcase_14 AC 98 ms
5,632 KB
testcase_15 AC 95 ms
5,504 KB
testcase_16 AC 111 ms
7,936 KB
testcase_17 AC 98 ms
5,760 KB
testcase_18 AC 77 ms
5,376 KB
testcase_19 AC 120 ms
8,064 KB
testcase_20 AC 76 ms
7,936 KB
testcase_21 WA -
testcase_22 AC 88 ms
8,064 KB
testcase_23 AC 86 ms
8,064 KB
testcase_24 AC 89 ms
8,064 KB
testcase_25 AC 89 ms
8,064 KB
testcase_26 AC 88 ms
8,064 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
const vector<int> dy={-1,0,1,0},dx={0,-1,0,1};
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T>void debag(const vector<T> &a){cerr<<"debag :";for(auto v:a)cerr<<v<<" ";cerr<<"\n";}
template<class T>void print(const vector<T> &a){for(auto v:a)cout<<v<<" ";cout<<"\n";}
// set:T,map:f  TxT→T =(T,f)
// set:E,map:h ExE→E =(E,h)
//map: g:TxE→T
//1-index
template <typename T,typename E>
struct lazysegtree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  lazysegtree(F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){}
  
  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  inline T reflect(int k){
    return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }
  inline void eval(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void thrust(int k){
    for(int i=height;i;i--) eval(k>>i);
  }
  inline void recalc(int k){    
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }
  void update(int a,int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }
  T query(int a,int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }
};
int main(){
    auto f=[](ll a,ll b){
        return min(a,b);
    };
    auto g=[](ll a,ll b){
        return a+b;
    };
    int n;
    cin>>n;
    V<ll> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
   lazysegtree<ll,ll> st(f,g,g,ll(1e10)+5,0);
   st.build(a);
   int q;
   cin>>q;
   while(q--){
       ll k,l,r,c;
       cin>>k>>l>>r>>c;
       if(k==1){
            st.update(l-1,r,c);
       }else{
           cout<<st.query(l-1,r)<<"\n";
       }
   }
}
0