結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ojisan_ITojisan_IT
提出日時 2018-06-14 17:02:10
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 150 ms / 5,000 ms
コード長 3,663 bytes
コンパイル時間 1,628 ms
コンパイル使用メモリ 172,224 KB
実行使用メモリ 6,236 KB
最終ジャッジ日時 2023-09-13 04:10:06
合計ジャッジ時間 3,999 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,212 KB
testcase_01 AC 4 ms
5,984 KB
testcase_02 AC 4 ms
6,212 KB
testcase_03 AC 4 ms
6,108 KB
testcase_04 AC 4 ms
6,032 KB
testcase_05 AC 4 ms
6,056 KB
testcase_06 AC 11 ms
6,132 KB
testcase_07 AC 5 ms
6,112 KB
testcase_08 AC 6 ms
6,164 KB
testcase_09 AC 69 ms
6,092 KB
testcase_10 AC 78 ms
6,108 KB
testcase_11 AC 42 ms
6,156 KB
testcase_12 AC 71 ms
6,052 KB
testcase_13 AC 14 ms
6,204 KB
testcase_14 AC 69 ms
5,988 KB
testcase_15 AC 90 ms
5,948 KB
testcase_16 AC 125 ms
6,092 KB
testcase_17 AC 150 ms
6,096 KB
testcase_18 AC 92 ms
6,236 KB
testcase_19 AC 89 ms
6,152 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
//const double PI = M_PI;  
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}

/*Coding Space*/
// ペアの全探索は a.begin(), a.begin() + n/2, a.end() として a[i],a[i+n/2](i = 0..n/2)
// This Segtree written by @qcw_pro(Retirement Maximum member).
template <class M, class O> // M: monoid, O: operator monoid
struct SegTree {
  using MM = function <M(M, M)>;
  using MO = function <M(M, O)>;
  using OO = function <O(O, O)>;
  using OI = function <O(O, int)>;
  const int n, h; // n: array size, h: height of tree
  const M m_id; // identity element of monoid
  const O o_id; // identity element of operator monoid
  MM mm; MO mo; OO oo; OI oi;
  vector<M> m; // monoid array
  vector<O> o; // operator monoid array
  SegTree(int n, M m_id, O o_id, MM mm, MO mo, OO oo,
          OI oi = [](const O& a, int b) { return a; })
    :n(n), h(sizeof(int)*CHAR_BIT - __builtin_clz(n)),
    m_id(m_id), o_id(o_id), mm(mm), mo(mo), oo(oo), oi(oi),
    m(n * 2, m_id), o(n * 2, o_id) {}
  
  inline void apply(int i, const O& v, int k) {
    m[i] = mo(m[i], oi(v, k));
    if(i < n) o[i] = oo(o[i], v);
  }
  inline void build(int i) {
    while(i >>= 1)
      if(o[i] == o_id)
        m[i] = mm(m[i * 2], m[i * 2 + 1]);
  }
  inline void push(int i) {
    int s{ i >> h ? h : h - 1 };
    for(int k{ 1 << (s - 1) }; s > 0; --s, k >>= 1) {
      int p{ i >> s };
      if(o[p] == o_id) continue;
      apply(p * 2, o[p], k);
      apply(p * 2 + 1, o[p], k);
      o[p] = o_id;
    }
  }
  void modify(int l, int r, const O& v) { // [l,r) 変更クエリ
    l += n, r += n;
    push(l), push(r - 1);
    int ll{ l }, rr{ r };
    for(int k{ 1 }; l < r; l >>= 1, r >>= 1, k <<= 1) {
      if(l & 1) apply(l++, v, k);
      if(r & 1) apply(r - 1, v, k);
    }
    build(ll), build(rr - 1);
  }
  M query(int l, int r) { // [l,r) 出力クエリ
    l += n, r += n;
    push(l), push(r - 1);
    M a{ m_id }, b{ m_id };
    for(; l < r; l >>= 1, r >>= 1) {
      if(l & 1) a = mm(a, m[l++]);
      if(r & 1) 
        b = mm(m[r - 1], b);
    }
    return mm(a, b);
  }
};
//SegTree<input type, operator type>   (size, M_I, O_I, MM, MO, OO, (OI))
const ll m_id = 0;
const ll o_id = 10000;
SegTree<ll, ll> a(100001, m_id, o_id,
                     plus<ll>(),
                     [](const ll a, const ll b) { return b; },
                     [](const ll a, const ll b) { return b; },
                     [](const ll a, const int k) { return (a == o_id)? a:a * k; });
int main(){
  int n,q; cin >> n >>q;
  ll ans_a = 0;
  ll ans_b = 0;
  rep(i,q){
    int x,l,r; cin >> x >> l >> r;
    if(x == 1){
      a.modify(l,++r,1);
    }else if(x == 2){
      a.modify(l,++r,1000000);
    }else{
      ll aq = a.query(l,++r);
      ll aa = aq % 1000000; ll bb = aq / 1000000;
      if(aa < bb)  ans_b += bb;
      if(aa > bb)  ans_a += aa;
    }
  }
    ll aq = a.query(0,n);
    ll aa = aq % 1000000; ll bb = aq / 1000000;
  cout << ans_a + aa << " " << ans_b + bb << endl;
}
0