結果
| 問題 | No.1074 増殖 |
| ユーザー |
 rokahikou1
|
| 提出日時 | 2021-06-05 12:47:53 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 276 ms / 2,000 ms |
| コード長 | 13,095 bytes |
| コンパイル時間 | 2,408 ms |
| コンパイル使用メモリ | 184,124 KB |
| 実行使用メモリ | 24,192 KB |
| 最終ジャッジ日時 | 2024-11-21 10:07:21 |
| 合計ジャッジ時間 | 5,114 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 21 ms
24,064 KB |
| testcase_01 | AC | 21 ms
24,064 KB |
| testcase_02 | AC | 20 ms
24,064 KB |
| testcase_03 | AC | 20 ms
24,064 KB |
| testcase_04 | AC | 20 ms
24,064 KB |
| testcase_05 | AC | 20 ms
24,064 KB |
| testcase_06 | AC | 123 ms
24,064 KB |
| testcase_07 | AC | 119 ms
24,192 KB |
| testcase_08 | AC | 145 ms
24,064 KB |
| testcase_09 | AC | 276 ms
24,064 KB |
| testcase_10 | AC | 119 ms
24,064 KB |
| testcase_11 | AC | 76 ms
24,064 KB |
| testcase_12 | AC | 77 ms
24,064 KB |
| testcase_13 | AC | 172 ms
23,936 KB |
| testcase_14 | AC | 170 ms
24,064 KB |
ソースコード
#pragma region Macros
#include <bits/stdc++.h>
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int(i) = (n)-1; (i) >= 0; (i)--)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define ROF(i, m, n) for(int(i) = (n)-1; (i) >= (m); (i)--)
#define ALL(v) (v).begin(), (v).end()
#define LLA(v) (v).rbegin(), (v).rend()
#define SZ(v) (int)(v).size()
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define DOUBLE(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define STRING(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VEC2(type, name, height, width) \
vector<vector<type>> name(height, vector<type>(width)); \
read(name)
#define DVEC(type, name1, name2, size) \
vector<type> name1(size), name2(size); \
read(name1, name2);
#define TVEC(type, name1, name2, name3, size) \
vector<type> name1(size), name2(size), name3(size); \
read(name1, name2, name3);
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;
const char newl = '\n';
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
template <class T> inline bool between(T x, T l, T r) { return l <= x && x < r; }
template <class T> inline vector<T> make_vec(size_t a, T val) { return vector<T>(a, val); }
template <class... Ts> inline auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec(ts...))>(a, make_vec(ts...)); }
void read() {}
template <class T> inline void read(T &a) { cin >> a; }
template <class T, class S> inline void read(pair<T, S> &p) { read(p.first), read(p.second); }
template <class T> inline void read(vector<T> &v) {
for(auto &&a : v) read(a);
}
template <class T, class U> inline void read(vector<T> &a, vector<U> &b) {
for(int i = 0; i < a.size(); i++) {
read(a[i]);
read(b[i]);
}
}
template <class T, class U, class V> inline void read(vector<T> &a, vector<U> &b, vector<V> &c) {
for(int i = 0; i < a.size(); i++) {
read(a[i]);
read(b[i]);
read(c[i]);
}
}
template <class Head, class... Tail> inline void read(Head &head, Tail &...tail) { read(head), read(tail...); }
template <class T> void write(const T &a) { cout << a << '\n'; }
template <class T> void write(const vector<T> &a) {
for(int i = 0; i < a.size(); i++) cout << a[i] << (i + 1 == a.size() ? '\n' : ' ');
}
template <class Head, class... Tail> void write(const Head &head, const Tail &...tail) {
cout << head << ' ';
write(tail...);
}
template <class T> void writel(const T &a) { cout << a << '\n'; }
template <class T> void writel(const vector<T> &a) {
for(int i = 0; i < a.size(); i++) cout << a[i] << '\n';
}
template <class Head, class... Tail> void writel(const Head &head, const Tail &...tail) {
cout << head << '\n';
write(tail...);
}
template <class T> auto sum(const vector<T> &a) { return accumulate(ALL(a), T(0)); }
template <class T> auto min(const vector<T> &a) { return *min_element(ALL(a)); }
template <class T> auto max(const vector<T> &a) { return *max_element(ALL(a)); }
template <class T, class U> void msort(vector<T> &a, vector<U> &b) {
assert(a.size() == b.size());
vector<pair<T, U>> ab(a.size());
for(int i = 0; i < a.size(); i++) ab[i] = {a[i], b[i]};
sort(ALL(ab));
for(int i = 0; i < a.size(); i++) {
a[i] = ab[i].first;
b[i] = ab[i].second;
}
}
template <class T, class U, class V> void msort(vector<T> &a, vector<U> &b, vector<V> &c) {
assert(a.size() == b.size() && b.size() == c.size());
vector<tuple<T, U, V>> abc(a.size());
for(int i = 0; i < a.size(); i++) abc[i] = {a[i], b[i], c[i]};
sort(ALL(abc));
for(int i = 0; i < a.size(); i++) {
a[i] = get<0>(abc[i]);
b[i] = get<1>(abc[i]);
c[i] = get<2>(abc[i]);
}
}
template <class T, class U> inline bool chmax(T &a, U b) {
if(a < b) {
a = b;
return 1;
}
return 0;
}
template <class T, class U> inline bool chmin(T &a, U b) {
if(a > b) {
a = b;
return 1;
}
return 0;
}
inline int bsf(int v) { return __builtin_ctz(v); } // 最下位の1が下から何番目か
inline int bsf(ll v) { return __builtin_ctzll(v); }
inline int bsr(int v) { return 31 - __builtin_clz(v); } // 最上位の1が下から何番目か
inline int bsr(ll v) { return 63 - __builtin_clzll(v); }
inline int lsb(int v) { return v & -v; } // 最上位の1だけ残す
inline ll lsb(ll v) { return v & -v; }
inline int msb(int v) { return 1 << bsr(v); } // 最上位の1だけ残す
inline ll msb(ll v) { return 1LL << bsr(v); }
struct IO {
IO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(10);
}
} io;
#pragma endregion
template <typename T> class SegmentTreeBeats {
const T inf = numeric_limits<T>::max();
int n, n2;
vector<T> f_max, s_max, max_n;
vector<T> f_min, s_min, min_n;
vector<T> sum;
vector<T> len, ladd, lval;
void update_node_max(int k, T x) {
sum[k] += (x - f_max[k]) * max_n[k];
if(f_max[k] == f_min[k]) {
f_max[k] = f_min[k] = x;
} else if(f_max[k] == s_min[k]) {
f_max[k] = s_min[k] = x;
} else {
f_max[k] = x;
}
if(lval[k] != inf && x < lval[k])
lval[k] = x;
}
void update_node_min(int k, T x) {
sum[k] += (x - f_min[k]) * min_n[k];
if(f_max[k] == f_min[k]) {
f_max[k] = f_min[k] = x;
} else if(s_max[k] == f_min[k]) {
s_max[k] = f_min[k] = x;
} else {
f_min[k] = x;
}
if(lval[k] != inf && lval[k] < x)
lval[k] = x;
}
void add_all(int k, T x) {
f_max[k] += x;
if(s_max[k] != -inf)
s_max[k] += x;
f_min[k] += x;
if(s_min[k] != inf)
s_min[k] += x;
sum[k] += len[k] * x;
if(lval[k] != inf) {
lval[k] += x;
} else
ladd[k] += x;
}
void update_all(int k, T x) {
f_max[k] = x;
s_max[k] = -inf;
f_min[k] = x;
s_min[k] = inf;
max_n[k] = min_n[k] = len[k];
sum[k] = x * len[k];
lval[k] = x;
ladd[k] = 0;
}
void push(int k) {
if(n2 - 1 <= k)
return;
if(lval[k] != inf) {
update_all(2 * k + 1, lval[k]);
update_all(2 * k + 2, lval[k]);
lval[k] = inf;
return;
}
if(ladd[k] != 0) {
add_all(2 * k + 1, ladd[k]);
add_all(2 * k + 2, ladd[k]);
ladd[k] = 0;
}
if(f_max[k] < f_max[2 * k + 1])
update_node_max(2 * k + 1, f_max[k]);
if(f_max[k] < f_max[2 * k + 2])
update_node_max(2 * k + 2, f_max[k]);
if(f_min[2 * k + 1] < f_min[k])
update_node_min(2 * k + 1, f_min[k]);
if(f_min[2 * k + 2] < f_min[k])
update_node_min(2 * k + 2, f_min[k]);
}
void update(int k) {
if(n2 - 1 <= k)
return;
sum[k] = sum[2 * k + 1] + sum[2 * k + 2];
if(f_max[2 * k + 1] < f_max[2 * k + 2]) {
f_max[k] = f_max[2 * k + 2];
max_n[k] = max_n[2 * k + 2];
s_max[k] = max(f_max[2 * k + 1], s_max[2 * k + 2]);
} else if(f_max[2 * k + 1] > f_max[2 * k + 2]) {
f_max[k] = f_max[2 * k + 1];
max_n[k] = max_n[2 * k + 1];
s_max[k] = max(s_max[2 * k + 1], f_max[2 * k + 2]);
} else {
f_max[k] = f_max[2 * k + 1];
max_n[k] = max_n[2 * k + 1] + max_n[2 * k + 2];
s_max[k] = max(s_max[2 * k + 1], s_max[2 * k + 2]);
}
if(f_min[2 * k + 1] < f_min[2 * k + 2]) {
f_min[k] = f_min[2 * k + 1];
min_n[k] = min_n[2 * k + 1];
s_min[k] = min(s_min[2 * k + 1], f_min[2 * k + 2]);
} else if(f_min[2 * k + 1] > f_min[2 * k + 2]) {
f_min[k] = f_min[2 * k + 2];
min_n[k] = min_n[2 * k + 2];
s_min[k] = min(f_min[2 * k + 1], s_min[2 * k + 2]);
} else {
f_min[k] = f_min[2 * k + 1];
min_n[k] = min_n[2 * k + 1] + min_n[2 * k + 2];
s_min[k] = min(s_min[2 * k + 1], s_min[2 * k + 2]);
}
}
void _update_min(T x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a || f_max[k] <= x)
return;
if(a <= l && r <= b && s_max[k] < x) {
update_node_max(k, x);
return;
}
push(k);
_update_min(x, a, b, 2 * k + 1, l, (l + r) / 2);
_update_min(x, a, b, 2 * k + 2, (l + r) / 2, r);
update(k);
}
void _update_max(T x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a || x <= f_min[k])
return;
if(a <= l && r <= b && x < s_min[k]) {
update_node_min(k, x);
return;
}
push(k);
_update_max(x, a, b, 2 * k + 1, l, (l + r) / 2);
_update_max(x, a, b, 2 * k + 2, (l + r) / 2, r);
update(k);
}
void _add_val(T x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a)
return;
if(a <= l && r <= b) {
add_all(k, x);
return;
}
push(k);
_add_val(x, a, b, 2 * k + 1, l, (l + r) / 2);
_add_val(x, a, b, 2 * k + 2, (l + r) / 2, r);
update(k);
}
void _update_val(T x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a)
return;
if(a <= l && r <= b) {
update_all(k, x);
return;
}
push(k);
_update_val(x, a, b, 2 * k + 1, l, (l + r) / 2);
_update_val(x, a, b, 2 * k + 2, (l + r) / 2, r);
update(k);
}
T _query_max(int a, int b, int k, int l, int r) {
if(b <= l || r <= a)
return -inf;
if(a <= l && r <= b) {
return f_max[k];
}
push(k);
T lv = _query_max(a, b, 2 * k + 1, l, (l + r) / 2);
T rv = _query_max(a, b, 2 * k + 2, (l + r) / 2, r);
return max(lv, rv);
}
T _query_min(int a, int b, int k, int l, int r) {
if(b <= l || r <= a)
return inf;
if(a <= l && r <= b) {
return f_min[k];
}
push(k);
T lv = _query_min(a, b, 2 * k + 1, l, (l + r) / 2);
T rv = _query_min(a, b, 2 * k + 2, (l + r) / 2, r);
return min(lv, rv);
}
T _query_sum(int a, int b, int k, int l, int r) {
if(b <= l || r <= a)
return 0;
if(a <= l && r <= b) {
return sum[k];
}
push(k);
T lv = _query_sum(a, b, 2 * k + 1, l, (l + r) / 2);
T rv = _query_sum(a, b, 2 * k + 2, (l + r) / 2, r);
return lv + rv;
}
public:
SegmentTreeBeats(int n) : SegmentTreeBeats(vector<T>(n)) {}
SegmentTreeBeats(const vector<T> &a) : n(a.size()) {
n2 = 1;
while(n2 < n)
n2 <<= 1;
f_max.assign(2 * n2, -inf);
s_max.assign(2 * n2, -inf);
max_n.resize(2 * n2);
f_min.assign(2 * n2, inf);
s_min.assign(2 * n2, inf);
min_n.resize(2 * n2);
sum.resize(2 * n2);
len.resize(2 * n2);
ladd.resize(2 * n2);
lval.assign(2 * n2, inf);
len[0] = n2;
for(int i = 0; i < n2 - 1; i++)
len[2 * i + 1] = len[2 * i + 2] = (len[i] >> 1);
for(int i = 0; i < n; i++) {
f_max[n2 - 1 + i] = f_min[n2 - 1 + i] = sum[n2 - 1 + i] = a[i];
max_n[n2 - 1 + i] = min_n[n2 - 1 + i] = 1;
}
for(int i = n2 - 2; i >= 0; i--) {
update(i);
}
}
void update_min(int a, int b, T x) { _update_min(x, a, b, 0, 0, n2); }
void update_max(int a, int b, T x) { _update_max(x, a, b, 0, 0, n2); }
void add_val(int a, int b, T x) { _add_val(x, a, b, 0, 0, n2); }
void update_val(int a, int b, T x) { _update_val(x, a, b, 0, 0, n2); }
T query_max(int a, int b) { return _query_max(a, b, 0, 0, n2); }
T query_min(int a, int b) { return _query_min(a, b, 0, 0, n2); }
T query_sum(int a, int b) { return _query_sum(a, b, 0, 0, n2); }
};
int main() {
INT(n);
SegmentTreeBeats<ll> bt1(20020), bt2(20020), bt3(20020), bt4(20020);
ll s = 0;
rep(i, n) {
INT(xa, ya, xb, yb);
bt1.update_max(0, xb, yb);
bt2.update_max(0, xb, -ya);
bt3.update_max(0, -xa, yb);
bt4.update_max(0, -xa, -ya);
ll ns = bt1.query_sum(0, 20010) + bt2.query_sum(0, 20010) + bt3.query_sum(0, 20010) + bt4.query_sum(0, 20010);
write(ns - s);
s = ns;
}
}