結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー 37kt_
提出日時 2016-11-19 23:09:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 126 ms / 5,000 ms
コード長 3,110 bytes
コンパイル時間 1,519 ms
コンパイル使用メモリ 171,744 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2024-11-27 06:23:13
合計ジャッジ時間 3,723 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

const int N = 1 << 17;

struct SegTree {
public:
  SegTree(){
    memset(seg, 0, sizeof(seg));
    memset(lazy, -1, sizeof(lazy));
  }
  
  void update(int l, int r, int x){
    update(l, r, x, 0, 0, N);
  }

  int query(int l, int r){
    return query(l, r, 0, 0, N);
  }

  void eval(int k, int a, int b){
    if (lazy[k] != -1){
      seg[k] = lazy[k] * (b - a);
      if (k * 2 + 1 < N * 2 - 1){
        lazy[k * 2 + 1] = lazy[k];
        lazy[k * 2 + 2] = lazy[k];
      }
      lazy[k] = -1;
    }
  }

  void update(int l, int r, int x, int k, int a, int b){
    eval(k, a, b);
    if (r <= a || b <= l) return;
    if (l <= a && b <= r){
      lazy[k] = x;
      eval(k, a, b);
      return;
    }
    int m = (a + b) / 2;
    update(l, r, x, k * 2 + 1, a, m);
    update(l, r, x, k * 2 + 2, m, b);
    seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2];
  }

  int query(int l, int r, int k, int a, int b){
    eval(k, a, b);
    if (r <= a || b <= l) return 0;
    if (l <= a && b <= r) return seg[k];
    int m = (a + b) / 2;
    int vl = query(l, r, k * 2 + 1, a, m);
    int vr = query(l, r, k * 2 + 2, m, b);
    seg[k] = seg[k * 2 + 1] + seg[k * 2 + 2];
    return vl + vr;
  }

private:
  int seg[N * 2 - 1], lazy[N * 2 - 1];
};

int main(){
  int n, q;
  cin >> n >> q;

  SegTree tr0, tr1;
  ll res0 = 0, res1 = 0;
  rep(q){
    int x, l, r;
    cin >> x >> l >> r, r++;
    if (x == 0){
      int v0 = tr0.query(l, r);
      int v1 = tr1.query(l, r);
      if (v0 > v1) res0 += v0;
      else if (v0 < v1) res1 += v1;
    }
    else if (x == 1){
      tr0.update(l, r, 1);
      tr1.update(l, r, 0);
    }
    else if (x == 2){
      tr0.update(l, r, 0);
      tr1.update(l, r, 1);
    }
  }

  res0 += tr0.query(0, n);
  res1 += tr1.query(0, n);
  cout << res0 << " " << res1 << endl;
}
0