#include #ifdef DEBUG #include #else #define dump(...) #endif /** * @docs input_tuple_vector.md */ template void input_tuple_vector_init(T &val, int N, std::index_sequence){ (void)std::initializer_list{ (void(std::get(val).resize(N)), 0)... }; } template void input_tuple_vector_helper(T &val, int i, std::index_sequence){ (void)std::initializer_list{ (void(std::cin >> std::get(val)[i]), 0)... }; } template auto input_tuple_vector(int N){ std::tuple...> ret; input_tuple_vector_init(ret, N, std::make_index_sequence()); for(int i = 0; i < N; ++i){ input_tuple_vector_helper(ret, i, std::make_index_sequence()); } return ret; } /** * @title SegmentTreeBeats * @docs segment_tree_beats.md */ class SegmentTreeBeats{ using value_type = int64_t; const int depth, size, hsize; std::vector fst_max, snd_max; std::vector max_count; std::vector fst_min, snd_min; std::vector min_count; std::vector sum, lazy_add; public: SegmentTreeBeats(int n): depth(n > 1 ? 32-__builtin_clz(n-1) + 1 : 1), size(1 << depth), hsize(size / 2), fst_max(size, std::numeric_limits::min()), snd_max(size, std::numeric_limits::min()), max_count(size, 0), fst_min(size, std::numeric_limits::max()), snd_min(size, std::numeric_limits::max()), min_count(size, 0), sum(size, 0), lazy_add(size, 0) {} private: inline int lc(int i) const {return i << 1 | 0;} // left child inline int rc(int i) const {return i << 1 | 1;} // right child inline void update_node_max(int i, value_type x){ sum[i] += (x - fst_max[i]) * max_count[i]; if(fst_max[i] == fst_min[i]) fst_max[i] = fst_min[i] = x; else if(fst_max[i] == snd_min[i]) fst_max[i] = snd_min[i] = x; else fst_max[i] = x; } inline void update_node_min(int i, value_type x){ sum[i] += (x - fst_min[i]) * min_count[i]; if(fst_max[i] == fst_min[i]) fst_max[i] = fst_min[i] = x; else if(snd_max[i] == fst_min[i]) snd_max[i] = fst_min[i] = x; else fst_min[i] = x; } inline void update_node_add(int i, value_type x){ const int len = hsize >> (31 - __builtin_clz(i)); sum[i] += x * len; fst_max[i] += x; if(snd_max[i] != std::numeric_limits::min()) snd_max[i] += x; fst_min[i] += x; if(snd_min[i] != std::numeric_limits::max()) snd_min[i] += x; lazy_add[i] += x; } inline void propagate(int i){ if(i >= hsize) return; if(lazy_add[i] != 0){ update_node_add(lc(i), lazy_add[i]); update_node_add(rc(i), lazy_add[i]); lazy_add[i] = 0; } if(fst_max[i] < fst_max[lc(i)]) update_node_max(lc(i), fst_max[i]); if(fst_min[i] > fst_min[lc(i)]) update_node_min(lc(i), fst_min[i]); if(fst_max[i] < fst_max[rc(i)]) update_node_max(rc(i), fst_max[i]); if(fst_min[i] > fst_min[rc(i)]) update_node_min(rc(i), fst_min[i]); } inline void bottom_up(int i){ const int L = lc(i); const int R = rc(i); sum[i] = sum[L] + sum[R]; fst_max[i] = std::max(fst_max[L], fst_max[R]); if(fst_max[L] < fst_max[R]){ max_count[i] = max_count[R]; snd_max[i] = std::max(fst_max[L], snd_max[R]); }else if(fst_max[L] > fst_max[R]){ max_count[i] = max_count[L]; snd_max[i] = std::max(snd_max[L], fst_max[R]); }else{ max_count[i] = max_count[L] + max_count[R]; snd_max[i] = std::max(snd_max[L], snd_max[R]); } fst_min[i] = std::min(fst_min[L], fst_min[R]); if(fst_min[L] > fst_min[R]){ min_count[i] = min_count[R]; snd_min[i] = std::min(fst_min[L], snd_min[R]); }else if(fst_min[L] < fst_min[R]){ min_count[i] = min_count[L]; snd_min[i] = std::min(snd_min[L], fst_min[R]); }else{ min_count[i] = min_count[L] + min_count[R]; snd_min[i] = std::min(snd_min[L], snd_min[R]); } } private: void chmin(int i, int l, int r, int s, int t, value_type x){ if(r <= s or t <= l or fst_max[i] <= x) return; if(s <= l and r <= t and snd_max[i] < x){ update_node_max(i, x); return; } propagate(i); chmin(lc(i), l, (l + r) / 2, s, t, x); chmin(rc(i), (l + r) / 2, r, s, t, x); bottom_up(i); } public: void chmin(int l, int r, value_type x){chmin(1, 0, hsize, l, r, x);} private: void chmax(int i, int l, int r, int s, int t, value_type x){ if(r <= s or t <= l or fst_min[i] >= x) return; if(s <= l and r <= t and snd_min[i] > x){ update_node_min(i, x); return; } propagate(i); chmax(lc(i), l, (l + r) / 2, s, t, x); chmax(rc(i), (l + r) / 2, r, s, t, x); bottom_up(i); } public: void chmax(int l, int r, value_type x){chmax(1, 0, hsize, l, r, x);} private: void add(int i, int l, int r, int s, int t, value_type x){ if(r <= s or t <= l) return; if(s <= l and r <= t){ update_node_add(i, x); return; } propagate(i); add(lc(i), l, (l + r) / 2, s, t, x); add(rc(i), (l + r) / 2, r, s, t, x); bottom_up(i); } public: void add(int l, int r, value_type x){add(1, 0, hsize, l, r, x);} private: value_type get_sum(int i, int l, int r, int s, int t){ if(r <= s or t <= l) return 0; if(s <= l and r <= t) return sum[i]; propagate(i); return get_sum(lc(i), l, (l + r) / 2, s, t) + get_sum(rc(i), (l + r) / 2, r, s, t); } public: value_type get_sum(int l, int r){return get_sum(1, 0, hsize, l, r);} public: void init_with_vector(const std::vector &v){ fst_max.assign(size, std::numeric_limits::min()); snd_max.assign(size, std::numeric_limits::min()); max_count.assign(size, 1); fst_min.assign(size, std::numeric_limits::max()); snd_min.assign(size, std::numeric_limits::max()); min_count.assign(size, 1); sum.assign(size, 0); lazy_add.assign(size, 0); for(int i = 0; i < (int)v.size(); ++i){ fst_max[hsize + i] = v[i]; max_count[hsize + i] = 1; fst_min[hsize + i] = v[i]; min_count[hsize + i] = 1; sum[hsize + i] = v[i]; } for(int i = hsize - 1; i > 0; --i) bottom_up(i); } void init(value_type value){ init_with_vector(std::vector(hsize, value)); } }; /** * @title 双対SegmentTree * @docs dual_segment_tree.md */ template class DualSegmentTree{ using value_type = typename Monoid::value_type; private: const int depth, size, hsize; std::vector data; inline void propagate(int i){ if(i < hsize){ data[i << 1 | 0] = Monoid::op(data[i], data[i << 1 | 0]); data[i << 1 | 1] = Monoid::op(data[i], data[i << 1 | 1]); data[i] = Monoid::id(); } } inline void propagate_top_down(int i){ std::vector temp; while(i > 1){ i >>= 1; temp.push_back(i); } for(auto it = temp.rbegin(); it != temp.rend(); ++it) propagate(*it); } public: DualSegmentTree(int n): depth(n > 1 ? 32-__builtin_clz(n-1) + 1 : 1), size(1 << depth), hsize(size / 2), data(size, Monoid::id()) {} inline void update(int l, int r, const value_type &x){ propagate_top_down(l + hsize); propagate_top_down(r + hsize); int L = l + hsize; int R = r + hsize; while(L < R){ if(R & 1) --R, data[R] = Monoid::op(x, data[R]); if(L & 1) data[L] = Monoid::op(x, data[L]), ++L; L >>= 1, R >>= 1; } } inline value_type get(int i){ propagate_top_down(i + hsize); return data[i + hsize]; } template inline void init_with_vector(const std::vector &a){ data.assign(size, Monoid::id()); for(int i = 0; i < (int)a.size(); ++i) data[hsize + i] = a[i]; } template inline void init(const T &val){ init_with_vector(std::vector(hsize, val)); } }; /** * @docs max.md */ template struct MaxMonoid{ using value_type = T; constexpr inline static value_type id(){return std::numeric_limits::lowest();} constexpr inline static value_type op(const value_type &a, const value_type &b){return std::max(a, b);} }; void f(int N, std::vector X, std::vector Y, std::vector &ans){ for(int i = 0; i < N; ++i) X[i] = std::abs(X[i]); for(int i = 0; i < N; ++i) Y[i] = std::abs(Y[i]); std::vector temp(N); SegmentTreeBeats seg(20001); DualSegmentTree> s(20001); seg.init(0); for(int i = 0; i < N; ++i){ if(s.get(X[i]) < Y[i]){ int lb = 0, ub = 20001; while(abs(lb - ub) > 1){ int mid = (lb + ub) / 2; if(s.get(mid) < Y[i]){ ub = mid; }else{ lb = mid; } } int j = ub; //dump(std::make_tuple(j, X[i] + 1, seg.get_sum(j, X[i] + 1))); temp[i] += (X[i] - j + 1) * Y[i] - seg.get_sum(j, X[i] + 1); } seg.chmax(0, X[i] + 1, Y[i]); s.update(0, X[i] + 1, Y[i]); } //dump(temp); for(int i = 0; i < N; ++i) ans[i] += temp[i]; } int main(){ int N; while(std::cin >> N){ auto [Xa, Ya, Xb, Yb] = input_tuple_vector(N); std::vector ans(N); f(N, Xa, Ya, ans); f(N, Xb, Ya, ans); f(N, Xa, Yb, ans); f(N, Xb, Yb, ans); for(auto a : ans){ std::cout << a << "\n"; } } return 0; }