結果

問題 No.1074 増殖
コンテスト
ユーザー yukudo
提出日時 2020-06-05 22:48:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 481 ms / 2,000 ms
コード長 3,135 bytes
コンパイル時間 1,719 ms
コンパイル使用メモリ 175,860 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-12-17 16:59:50
合計ジャッジ時間 6,119 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}


// 初期状態は全て 0
// - 区間 [l, r) を値 v で更新
// - 範囲 [l, r) の和を取得
// 遅延評価セグツリーによる実装
struct RangeUpdateRangeSum {
  using Val = ll;
  int n;
  vector<Val> seg;
  vector<Val> lazy;
  const Val UNITY_LAZY = -1;
  void clear(int N) {
    for (n = 1; n < N; n <<= 1);
    seg.assign(n * 2, 0);
    lazy.assign(n * 2, UNITY_LAZY);
    seg[1] = 0; // 初期値
  }

  void eval_lazy(int nl, int nr, int k) {
    if (lazy[k] != UNITY_LAZY) {
      seg[k] = (nr - nl) * lazy[k];
      if (nr - nl >= 2) {
        lazy[2*k  ] = lazy[k];
        lazy[2*k+1] = lazy[k];
      }
      lazy[k] = UNITY_LAZY;
    }
  }
  // [l, r) の和
  Val getSum(int l, int r) {
    if (r - l <= 0) return 0;
    return getSum(0, n, 1, l, r);
  }
  Val getSum(int nl, int nr, int k, int l, int r) {
    eval_lazy(nl, nr, k);
    if (r <= nl || nr <= l) return 0;
    if (l <= nl && nr <= r) {
      return seg[k];
    }
    Val x = getSum(nl, (nl+nr)/2, 2*k  , l, r);
    Val y = getSum((nl+nr)/2, nr, 2*k+1, l, r);
    return x + y;
  }

  // [l, r) の全てを val で更新
  void updateRange(int l, int r, Val val) {
    updateRange(0, n, 1, l, r, val);
  }
  void updateRange(int nl, int nr, int k, int l, int r, Val val) {
    eval_lazy(nl, nr, k);
    if (r <= nl || nr <= l) return;
    if (l <= nl && nr <= r) { lazy[k] = val; eval_lazy(nl, nr, k); return; }
    updateRange(nl, (nl+nr)/2, 2*k  , l, r, val);
    updateRange((nl+nr)/2, nr, 2*k+1, l, r, val);
    seg[k] = seg[2*k] + seg[2*k+1];
  }
};

int main2() {

  RangeUpdateRangeSum segTree[4];

  const int MAX_C = 41234;
  REP(i, 4) segTree[i].clear(MAX_C);

  int N = nextLong();

  REP(i, N) {
    int Xa = nextLong();
    int Ya = nextLong();
    int Xb = nextLong();
    int Yb = nextLong();


    int Xs[4] = { Xb, abs(Xa), abs(Xa), Xb };
    int Ys[4] = { Yb, Yb,      abs(Ya), abs(Ya) };

    ll ans = 0;
    REP(i, 4) {
      const int X = Xs[i];
      const int Y = Ys[i];

      ll x = segTree[i].getSum(0, X);
      ll hi = MAX_C;
      ll lo = -1;
      while (hi - lo > 1) {
        ll mi = (hi + lo) / 2;
        if (Y > segTree[i].getSum(mi, mi+1)) {
          hi = mi;
        } else {
          lo = mi;
        }
      }
      if (hi < X) {
        segTree[i].updateRange(hi, X, Y);
      }
      ll y = segTree[i].getSum(0, X);
      ans += y - x;
      // cout << "i=" << i << "  +" << y-x << endl;
    }
    cout << ans << endl;
  }
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}
0