結果

問題 No.1074 増殖
ユーザー どららどらら
提出日時 2020-06-05 23:55:57
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 952 ms / 2,000 ms
コード長 4,437 bytes
コンパイル時間 2,137 ms
コンパイル使用メモリ 180,884 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-05-10 00:22:54
合計ジャッジ時間 9,011 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,296 KB
testcase_01 AC 5 ms
7,424 KB
testcase_02 AC 5 ms
7,296 KB
testcase_03 AC 5 ms
7,296 KB
testcase_04 AC 5 ms
7,296 KB
testcase_05 AC 5 ms
7,296 KB
testcase_06 AC 777 ms
7,424 KB
testcase_07 AC 542 ms
7,296 KB
testcase_08 AC 653 ms
7,424 KB
testcase_09 AC 952 ms
7,296 KB
testcase_10 AC 492 ms
7,424 KB
testcase_11 AC 514 ms
7,296 KB
testcase_12 AC 505 ms
7,296 KB
testcase_13 AC 680 ms
7,296 KB
testcase_14 AC 691 ms
7,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

template <class Monoid, class OpMonoid>
class LazySegmentTree {
  using FuncMM = std::function<Monoid(Monoid, Monoid)>;
  using FuncMO = std::function<Monoid(Monoid, OpMonoid, int)>;
  using FuncOO = std::function<OpMonoid(OpMonoid, OpMonoid)>;

  const FuncMM funcMM;
  const FuncMO funcMO;
  const FuncOO funcOO;
  const Monoid monoidIdentity;
  const OpMonoid opMonoidIdentity;

  int N;
  std::vector<Monoid> dat;
  std::vector<OpMonoid> lazy;

  void setLazy(int k, const OpMonoid& om) { lazy[k] = funcOO(lazy[k], om); }
  void push(int k, int len) {
    if (lazy[k] == opMonoidIdentity) return;
    if (k < N) {
      setLazy(2 * k + 0, lazy[k]);
      setLazy(2 * k + 1, lazy[k]);
    }
    dat[k] = funcMO(dat[k], lazy[k], len);
    lazy[k] = opMonoidIdentity;
  }

 public:
  LazySegmentTree(int n, const FuncMM funcMM, const FuncMO funcMO,
                  const FuncOO funcOO, const Monoid monoidIdentity,
                  const OpMonoid opMonoidIdentity)
      : funcMM(funcMM),
        funcMO(funcMO),
        funcOO(funcOO),
        monoidIdentity(monoidIdentity),
        opMonoidIdentity(opMonoidIdentity) {
    N = 1;
    while (N < n) N *= 2;
    dat.resize(2 * N, monoidIdentity);
    lazy.resize(2 * N, opMonoidIdentity);
  }

  void dump() {
    std::cout << "dat: ";
    for (int i = 1; i < dat.size(); i++) {
      if (i == N) std::cout << "| ";
      std::cout << dat[i].ai << "(" << lazy[i].p << "," << lazy[i].q << ","
                << lazy[i].r << ") ";
    }
    std::cout << std::endl;
  }

  void set(int i, const Monoid& v) { dat[N + i] = v; }

  void init() {
    for (int i = N - 1; i > 0; i--) {
      dat[i] = funcMM(dat[2 * i + 0], dat[2 * i + 1]);
    }
  }

  void update(int s, int t, const OpMonoid& om) { update(s, t, om, 1, 0, N); }
  void update(int s, int t, const OpMonoid& om, int k, int l, int r) {
    push(k, r - l);
    if (r <= s || t <= l) return;
    if (s <= l && r <= t) {
      setLazy(k, om);
      push(k, r - l);
      return;
    }
    update(s, t, om, 2 * k + 0, l, (l + r) / 2);
    update(s, t, om, 2 * k + 1, (l + r) / 2, r);
    dat[k] = funcMM(dat[2 * k + 0], dat[2 * k + 1]);
  }

  Monoid query(int s, int t) { return query(s, t, 1, 0, N); }
  Monoid query(int s, int t, int k, int l, int r) {
    push(k, r - l);
    if (r <= s || t <= l) return monoidIdentity;
    if (s <= l && r <= t) return dat[k];
    Monoid vl = query(s, t, 2 * k + 0, l, (l + r) / 2);
    Monoid vr = query(s, t, 2 * k + 1, (l + r) / 2, r);
    return funcMM(vl, vr);
  }
};

struct VAL {
  ll ai;
};

struct OP {
  ll p;
};
bool operator==(const OP& a, const OP& b) {
  return a.p == b.p;
}

int find_i(LazySegmentTree<VAL, OP>& lst, ll h){
  int lb = -1, ub = 20003;
  while(ub-lb>1){
    int mid = (lb+ub)/2;

    if(lst.query(mid,mid+1).ai >= h) lb = mid;
    else ub = mid;
  }
  return ub;
}

ll solve(LazySegmentTree<VAL, OP>& lst, int x, int y){
  x--;
  int xx = find_i(lst, y);
  if(x < xx) return 0;
  ll w = x+1-xx;
  ll sum = lst.query(xx,x+1).ai;
  ll ret = w * y - sum;

  OP op;
  op.p = y; 
  lst.update(xx,x+1,op);

  return ret;
}

int main(){
  auto funcMM = [](const VAL& a, const VAL& b) {
    VAL ret;
    ret.ai = a.ai + b.ai;
    return ret;
  };
  auto funcMO = [](const VAL& a, const OP& b, int k) {
    VAL ret;
    ret.ai = b.p * k;
    return ret;
  };
  auto funcOO = [](const OP& a, const OP& b) {
    OP ret;
    ret.p = max(a.p, b.p);
    return ret;
  };

  LazySegmentTree<VAL, OP> lst1(20005, funcMM, funcMO, funcOO, (VAL){0}, (OP){0});
  LazySegmentTree<VAL, OP> lst2(20005, funcMM, funcMO, funcOO, (VAL){0}, (OP){0});
  LazySegmentTree<VAL, OP> lst3(20005, funcMM, funcMO, funcOO, (VAL){0}, (OP){0});
  LazySegmentTree<VAL, OP> lst4(20005, funcMM, funcMO, funcOO, (VAL){0}, (OP){0});

  int N;
  cin >> N;
  rep(i,N){
    int Xa, Ya, Xb, Yb;
    cin >> Xa >> Ya >> Xb >> Yb;

    ll a = solve(lst1, Xb, Yb);
    ll b = solve(lst2, Xb, -Ya);
    ll c = solve(lst3, -Xa, -Ya);
    ll d = solve(lst4, -Xa, Yb);
    
    ll sum = a+b+c+d;
    //cout << a << " " << b << " " << c << " " << d << endl;
    
    cout << sum << endl;
  }
  
  
  return 0;
}
0