結果

問題 No.1000 Point Add and Array Add
ユーザー HyadoHyado
提出日時 2020-02-28 21:53:39
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 310 ms / 2,000 ms
コード長 4,494 bytes
コンパイル時間 2,114 ms
コンパイル使用メモリ 173,612 KB
実行使用メモリ 20,836 KB
最終ジャッジ日時 2024-04-21 18:24:07
合計ジャッジ時間 6,232 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 4 ms
6,940 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 4 ms
6,940 KB
testcase_15 AC 3 ms
6,940 KB
testcase_16 AC 193 ms
18,356 KB
testcase_17 AC 174 ms
13,056 KB
testcase_18 AC 310 ms
20,764 KB
testcase_19 AC 298 ms
20,716 KB
testcase_20 AC 186 ms
20,696 KB
testcase_21 AC 288 ms
20,836 KB
testcase_22 AC 243 ms
20,820 KB
testcase_23 AC 294 ms
20,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
using ld = long double;
template<typename T> using V = vector<T>;
template<typename T> using VV = vector<vector<T>>;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,a,n) for(ll i=a;i<(ll)(n);++i)
#define repr(i,a,n) for(ll i=n-1;(ll)a<=i;--i)
#define ENDL '\n'
typedef pair<int,int> Pi;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
const ll LINF = (ll)(1e18 +99);
const vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
template<typename T,typename U> inline bool chmin(T& t, const U& u){if(t>u){t=u;return 1;}return 0;}
template<typename T,typename U> inline bool chmax(T& t, const U& u){if(t<u){t=u;return 1;}return 0;}
template<typename T> inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T,typename Y> inline T mpow(T a, Y n) {
  T res = 1;
  for(;n;n>>=1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}

template<typename T,T(F_dd)(T,T),T(F_dl)(T,T),T(F_ll)(T,T)>
//dat-dat dat-lazy lazy-lazy min,add,addなどを入れる
struct Lazysegtree{
    int sz,ex;
    T ini_d,ini_l;//default値
    vector<T> dat,laz;
    vector<bool> need;

    Lazysegtree(int n,T _ini_d,T _ini_l) : Lazysegtree(vector<T>(n,_ini_d),_ini_d,_ini_l){}
    Lazysegtree(vector<T> init,T _ini_d, T _ini_l) : ini_d(_ini_d),ini_l(_ini_l){
        int n=(int)(init.size());
        ex=1;
        while((1<<ex) < n)ex++;
        sz=(1<<ex);//最下層のノード数になる
        
        dat=vector<T>(2*sz-1,ini_d);
        laz=vector<T>(2*sz-1,ini_l);
        need=vector<bool>(2*sz-1,false);
        for (int i = 0; i < n; i++) dat[sz + i -1] = init[i];//最下層以外のノード数はsz-1
        for (int i = sz-2; i >= 0; i--) {
            update(i);
        }//上層のノードの初期化
    }

    void update(int k){dat[k]=F_dd(dat[2*k+1],dat[2*k+2]);}//上層ノードの更新

    void seg_upd(int k,T x){//区間ノードに対する更新
        dat[k] = F_dl(dat[k],x);
        laz[k] = F_ll(laz[k],x);
        need[k]=true;
    }

    void eval(int k){//子の区間に伝播させる
        if(!need[k])return;

        seg_upd(2*k+1,laz[k]);
        seg_upd(2*k+2,laz[k]);
        laz[k]=ini_l;
        need[k]=false;
    }

    //区間[a,b)に対する取得クエリ [l,r)はノード番号kに対応する区間
    T get_q(int a,int b,int l,int r,int k){
        if(b<=l || r<=a) return 0;
        if(a<=l && r<=b) return dat[k];
        eval(k);//ノードを見たので遅延を一段階伝播させておく
        return F_dd(get_q(a,b,l,(l+r)/2,2*k+1),get_q(a,b,(l+r)/2,r,2*k+2));
    }
    T get_q(int a,int b){return get_q(a,b,0,sz,0);}


    //区間[a,b)に対する更新クエリ
    void up_q(int a,int b,T x,int l,int r,int k){
        if(b<=l || r<=a) return;
        if(a<=l && r<=b){
            seg_upd(k,x);
            return;
        }

        //子ノードを見る必要がある場合
        eval(k);
        up_q(a,b,x,l,(l+r)/2,2*k+1);
        up_q(a,b,x,(l+r)/2,r,2*k+2);
        update(k);//更新終了後、親も更新
    }
    void up_q(int a,int b,T x){up_q(a,b,x,0,sz,0);}
};//初期値の設定に注意（完全二分木にするために拡張した部分の初期値もini_dになる）
//区間minmaxクエリに対しては拡張したノードの初期値をよしなに設定する必要あり


ll my_max(ll a,ll b){return max(a,b);}
ll my_add(ll a,ll b){return a+b;}


signed main(){
  cin.tie(0);ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);
  ll n,q;cin>>n>>q;
  V<ll> a(n),ans(n,0);
  rep(i,0,n)cin>>a[i];

  V<ll> typ(q),l(q),r(q);
  rep(i,0,q){
    char c;
    cin>>c>>l[i]>>r[i];
    l[i]--;
    if(c=='A')typ[i]=0;
    else {
      typ[i]=1;
      r[i]--;
    }
  }

  Lazysegtree<ll,my_max,my_add,my_add> s(n,0,0);
  repr(i,0,q){
    if(typ[i]){
      s.up_q(l[i],r[i]+1,1);
    }else{
      ans[l[i]]+=s.get_q(l[i],l[i]+1)*r[i];
    }

  }

  rep(i,0,n){
    ans[i]+=s.get_q(i,i+1)*a[i];
  }

  rep(i,0,n){
    cout<<ans[i]<<" ";
  }cout<<ENDL;
  
}
//( . _ . ) PUE
//CHECK overflow,vector_size,what to output?
0