結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ojisan_ITojisan_IT
提出日時 2018-06-14 17:06:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 76 ms / 5,000 ms
コード長 5,572 bytes
コンパイル時間 1,784 ms
コンパイル使用メモリ 175,988 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-30 14:24:32
合計ジャッジ時間 2,953 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,812 KB
testcase_01 AC 4 ms
6,944 KB
testcase_02 AC 4 ms
6,944 KB
testcase_03 AC 4 ms
6,944 KB
testcase_04 AC 4 ms
6,940 KB
testcase_05 AC 4 ms
6,940 KB
testcase_06 AC 7 ms
6,940 KB
testcase_07 AC 4 ms
6,940 KB
testcase_08 AC 5 ms
6,944 KB
testcase_09 AC 37 ms
6,944 KB
testcase_10 AC 32 ms
6,940 KB
testcase_11 AC 24 ms
6,940 KB
testcase_12 AC 37 ms
6,940 KB
testcase_13 AC 9 ms
6,940 KB
testcase_14 AC 17 ms
6,940 KB
testcase_15 AC 35 ms
6,940 KB
testcase_16 AC 56 ms
6,940 KB
testcase_17 AC 76 ms
6,940 KB
testcase_18 AC 32 ms
6,944 KB
testcase_19 AC 47 ms
6,944 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);
  }
};
struct Fcin {
    template <class T>
    inline void get(T& v) {
        int s{}, c;
        do { c = getchar_unlocked(); } while(c <= 32 || 126 < c);
        if(c == '-') s = 1, c = getchar_unlocked();
        for(v = 0; 47 < c && c < 58; c = getchar_unlocked())
            v = (v << 1) + (v << 3) + c - 48;
        if(s) v = -v;
    }
    template <class T>
    Fcin& operator>>(T& v) { cin >> v; return *this; }
    Fcin& operator>>(int& v) { get(v); return *this; }
    Fcin& operator>>(long long& v) { get(v); return *this; }
    Fcin& operator>>(char& v) { v = getchar_unlocked(); return *this; }
    Fcin& operator>>(char* v) {
        do { *v = getchar_unlocked(); } while(*v <= 32 || 126 < *v);
        while(32 < *v && *v < 127) *++v = getchar_unlocked();
        *v = 0;
        return *this;
    }
    Fcin& operator>>(string& v) {
        v.clear(); auto p = back_inserter(v); char c;
        do { c = getchar_unlocked(); } while(c <= 32 || 126 < c);
        *p = c, c = getchar_unlocked();
        while(32 < c && c < 127) *++p = c, c = getchar_unlocked();
        return *this;
    }
};
struct Fcout {
    char buf[32];
    template <class T>
    inline void put(T v) {
        if(!v) { putchar_unlocked('0'); return; }
        if(v < 0) putchar_unlocked('-'), v = -v;
        int i{};
        for(; v; v /= 10) buf[i++] = v % 10 + 48;
        while(i) putchar_unlocked(buf[--i]);
    }
    template <class T>
    Fcout& operator<<(const T& v) { cout << v; return *this; }
    Fcout& operator<<(const int& v) { put(v); return *this; }
    Fcout& operator<<(const long long& v) { put(v); return *this; }
    Fcout& operator<<(const char& v) { putchar_unlocked(v); return *this; }
    Fcout& operator<<(const char* v) {
        while(*v) putchar_unlocked(*v++);
        return *this;
    }
    Fcout& operator<<(const string& v) { operator<<(v.c_str()); return *this; }
};
Fcin fcin;
Fcout fcout;
//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; fcin >> 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;
  fcout << ans_a + aa << ' ' << ans_b + bb << '\n';
}
0