結果

問題 No.1074 増殖
コンテスト
ユーザー chocopuu
提出日時 2020-06-06 01:59:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,269 bytes
コンパイル時間 3,217 ms
コンパイル使用メモリ 205,404 KB
最終ジャッジ日時 2025-01-10 23:11:08
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define int long long
using i64 = long long;
#define REP(i, n) for (int i = 0; i < (int)n; ++i)
#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;}
template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;}
constexpr int INF = 1e18;

template <typename T,typename E, typename F, typename G, typename H>
struct SegmentTree{
  //using F = function<T(T,T)>;
  //using G = function<T(T,E)>;
  //using H = function<E(E,E)>;
  int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(F f,G g,H h,T ti,E ei):
	f(f),g(g),h(h),ti(ti),ei(ei){}

  void init(int n_){
	n=1;height=0;
	while(n<n_) n<<=1,height++;
	dat.assign(2*n,ti);
	laz.assign(2*n,ei);
  }

  void build(const vector<T> &v){
	int n_=v.size();
	init(n_);
	for(int i=0;i<n_;i++) dat[n+i]=v[i];
	for(int i=n-1;i;i--)
	  dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  inline T reflect(int k){
	return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }

  inline void propagate(int k){
	if(laz[k]==ei) return;
	laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
	laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
	dat[k]=reflect(k);
	laz[k]=ei;
  }

  inline void thrust(int k){
	for(int i=height;i;i--) propagate(k>>i);
  }

  inline void recalc(int k){
	while(k>>=1)
	  dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }

  void update(int a,int b,E x){
	if(a>=b) return;
	thrust(a+=n);
	thrust(b+=n-1);
	for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
	  if(l&1) laz[l]=h(laz[l],x),l++;
	  if(r&1) --r,laz[r]=h(laz[r],x);
	}
	recalc(a);
	recalc(b);
  }

  void set_val(int a,T x){
	thrust(a+=n);
	dat[a]=x;laz[a]=ei;
	recalc(a);
  }

  T query(int a,int b){
	if(a>=b) return ti;
	thrust(a+=n);
	thrust(b+=n-1);
	T vl=ti,vr=ti;
	for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
	  if(l&1) vl=f(vl,reflect(l++));
	  if(r&1) vr=f(reflect(--r),vr);
	}
	return f(vl,vr);
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){
	if(l+1==r){
	  acc=f(acc,reflect(k));
	  return check(acc)?k-n:-1;
	}
	propagate(k);
	int m=(l+r)>>1;
	if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
	if(st<=l&&!check(f(acc,dat[k]))){
	  acc=f(acc,dat[k]);
	  return -1;
	}
	int vl=find(st,check,acc,(k<<1)|0,l,m);
	if(~vl) return vl;
	return find(st,check,acc,(k<<1)|1,m,r);
  }

  template<typename C>
  int find(int st,C &check){
	T acc=ti;
	return find(st,check,acc,1,0,n);
  }
  //アウトの条件を渡す
};
//SegmentTree<int, int, decltype(f), decltype(g), decltype(h)> seg(f,g,h,ti,ei);

signed main() {
	i64 N;
	cin >> N;
	vector<i64>xa(N), ya(N), xb(N), yb(N);
	REP(i, N) {
		cin >> xa[i] >> ya[i] >> xb[i] >> yb[i];
	}
	vector<i64> ans(N);
	auto func = [&](vector<i64>&x, vector<i64>&y) -> void {
		auto f = [&](i64 a, i64 b) {return a + b;};
		auto g = [&](i64 a, i64 b) {return max(a, b);};
		auto h = [&](i64 a, i64 b) {return max(a, b);};
		SegmentTree<i64, i64, decltype(f), decltype(g), decltype(h)> seg(f,g,h,0ll,0ll);
		auto ma = [&](i64 a, i64 b) {return max(a, b);};
		auto mi = [&](i64 a, i64 b) {return min(a, b);};
		SegmentTree<int, int, decltype(mi), decltype(ma), decltype(ma)> segmax(mi,ma,ma,INF,0ll);
		seg.build(vector<i64>(20020));
		segmax.build(vector<i64>(20020));
		i64 tar, ret = 0;
		auto check = [&](i64 x) {return x < tar;};
		REP(i, N) {
			tar = y[i];
			i64 idx = segmax.find(0, check);
			CHMIN(idx, x[i]);
			ret += y[i] * (x[i] - idx) - seg.query(idx, x[i]);
			seg.update(idx, x[i], y[i]);
			segmax.update(idx, x[i], y[i]);
			ans[i] += ret;
		}
	};
	vector<vector<i64>>x(4,vector<i64>(N)),y(4,vector<i64>(N));
	REP(i, N) {
		x[0][i] = -xa[i], y[0][i] = -ya[i];
		x[1][i] = -xa[i], y[1][i] = yb[i];
		x[2][i] = xb[i], y[2][i] = -ya[i];
		x[3][i] = xb[i], y[3][i] = yb[i];
	}
	REP(i, 4) func(x[i], y[i]);
	RREP(i, N - 1) ans[i + 1] -= ans[i];
	REP(i, N) cout << ans[i] << endl;
}
0