結果
| 問題 | No.1074 増殖 |
| ユーザー |
 Haar
|
| 提出日時 | 2020-06-05 22:41:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 871 ms / 2,000 ms |
| コード長 | 9,660 bytes |
| コンパイル時間 | 6,122 ms |
| コンパイル使用メモリ | 214,148 KB |
| 最終ジャッジ日時 | 2025-01-10 22:46:19 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 |
ソースコード
#include <bits/stdc++.h>
#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...)
#endif
/**
* @docs input_tuple_vector.md
*/
template <typename T, size_t ... I>
void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>){
(void)std::initializer_list<int>{
(void(std::get<I>(val).resize(N)), 0)...
};
}
template <typename T, size_t ... I>
void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>){
(void)std::initializer_list<int>{
(void(std::cin >> std::get<I>(val)[i]), 0)...
};
}
template <typename ... Args>
auto input_tuple_vector(int N){
std::tuple<std::vector<Args>...> ret;
input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
for(int i = 0; i < N; ++i){
input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
}
return ret;
}
/**
* @title SegmentTreeBeats
* @docs segment_tree_beats.md
*/
class SegmentTreeBeats{
using value_type = int64_t;
const int depth, size, hsize;
std::vector<value_type> fst_max, snd_max;
std::vector<int> max_count;
std::vector<value_type> fst_min, snd_min;
std::vector<int> min_count;
std::vector<value_type> 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<value_type>::min()),
snd_max(size, std::numeric_limits<value_type>::min()),
max_count(size, 0),
fst_min(size, std::numeric_limits<value_type>::max()),
snd_min(size, std::numeric_limits<value_type>::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<value_type>::min()) snd_max[i] += x;
fst_min[i] += x;
if(snd_min[i] != std::numeric_limits<value_type>::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<value_type> &v){
fst_max.assign(size, std::numeric_limits<value_type>::min());
snd_max.assign(size, std::numeric_limits<value_type>::min());
max_count.assign(size, 1);
fst_min.assign(size, std::numeric_limits<value_type>::max());
snd_min.assign(size, std::numeric_limits<value_type>::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<value_type>(hsize, value));
}
};
/**
* @title 双対SegmentTree
* @docs dual_segment_tree.md
*/
template <typename Monoid>
class DualSegmentTree{
using value_type = typename Monoid::value_type;
private:
const int depth, size, hsize;
std::vector<value_type> 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<int> 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 <typename T>
inline void init_with_vector(const std::vector<T> &a){
data.assign(size, Monoid::id());
for(int i = 0; i < (int)a.size(); ++i) data[hsize + i] = a[i];
}
template <typename T>
inline void init(const T &val){
init_with_vector(std::vector<value_type>(hsize, val));
}
};
/**
* @docs max.md
*/
template <typename T>
struct MaxMonoid{
using value_type = T;
constexpr inline static value_type id(){return std::numeric_limits<T>::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<int> X, std::vector<int> Y, std::vector<int64_t> &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<int64_t> temp(N);
SegmentTreeBeats seg(20001);
DualSegmentTree<MaxMonoid<int>> 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<int, int, int, int>(N);
std::vector<int64_t> 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;
}