結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー hashiryo
提出日時 2019-05-30 19:37:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 342 ms / 5,000 ms
コード長 2,820 bytes
コンパイル時間 1,548 ms
コンパイル使用メモリ 174,096 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-09-17 16:08:41
合計ジャッジ時間 4,747 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> Pll;
typedef vector<ll> vll;
const ll INF = LLONG_MAX/10;
const ll MOD = 1e9+7;


template <typename T,typename E>
class LazySegmentTree{
private:
    typedef function<T(T,T)> F;
    typedef function<T(T,E)> G;
    typedef function<E(E,E)> H;
    typedef function<E(E,int)> P;
    int n;
    F f;
    G g;
    H h;
    T ti;
    E ei;
    P p;
    vector<T> dat;
    vector<E> laz;
    inline void eval(int len,int k){
        if(laz[k]==ei) return;
        if(k*2+1<n*2-1){
            laz[k*2+1]=h(laz[k*2+1],laz[k]);
            laz[k*2+2]=h(laz[k*2+2],laz[k]);
        }
        dat[k]=g(dat[k],p(laz[k],len));
        laz[k]=ei;
    }
public:
    LazySegmentTree(F f,G g,H h,T ti,E ei,P p=[](E a,int b){return a;}):
    f(f),g(g),h(h),ti(ti),ei(ei),p(p){}
    void init(int n_){
        n=1;
        while(n<n_) n<<=1;
        dat.assign(2*n-1,ti);
        laz.assign(2*n-1,ei);
    }
    void build(vector<T> v){
        int n_=v.size();
        init(n_);
        for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
        for(int i=n-2;i>=0;i--)
            dat[i]=f(dat[i*2+1],dat[i*2+2]);
    }
    T update(int a,int b,E x,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        eval(r-l,k);
        if(r<=a||b<=l) return dat[k];
        if(a<=l&&r<=b){
            laz[k]=h(laz[k],x);
            return g(dat[k],p(laz[k],r-l));
        }
        return dat[k]=f(update(a,b,x,k*2+1,l,(l+r)/2),
                        update(a,b,x,k*2+2,(l+r)/2,r));
    }
    T query(int a,int b,int k=0,int l=0,int r=-1){
        if(r<0)r=n;
        eval(r-l,k);
        if(r<=a||b<=l) return ti;
        if(a<=l&&r<=b) return dat[k];
        T vl=query(a,b,k*2+1,l,(l+r)/2);
        T vr=query(a,b,k*2+2,(l+r)/2,r);
        return f(vl,vr);
    }
    T operator[](const int &k) {return query(k,k+1);}
};



int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N;cin>>N;
  ll Q;cin>>Q;
  vector<LazySegmentTree<ll,ll> > seg(2,LazySegmentTree<ll,ll>([](ll a,ll b){return a+b;},[](ll a,ll b){return b<0?a:b;},[](ll a,ll b){return b<0?a:b;},0ll,-1,[](ll a,int b){return a*b;}));
  seg[0].init(N);
  seg[1].init(N);
  ll score[2]={0};
  for(ll q=0;q<Q;q++){
    ll x,l,r;cin>>x>>l>>r;
    if(x){
      seg[x&1].update(l,r+1,1);
      seg[!(x&1)].update(l,r+1,0);
    }else{
      ll a[2]={seg[0].query(l,r+1),seg[1].query(l,r+1)};
      if(a[0]>a[1]){
        score[0]+=a[0];
      }else if(a[0]<a[1]){
        score[1]+=a[1];
      }
    }
  }
  cout<<score[1]+seg[1].query(0,N)<<" "<<score[0]+seg[0].query(0,N)<<endl;
  return 0;
}
0