結果
| 問題 |
No.1074 増殖
|
| コンテスト | |
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2020-06-05 23:33:37 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 371 ms / 2,000 ms |
| コード長 | 8,780 bytes |
| コンパイル時間 | 3,343 ms |
| コンパイル使用メモリ | 205,104 KB |
| 最終ジャッジ日時 | 2025-01-10 23:01:29 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:252:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
252 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
main.cpp:259:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
259 | scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
if(b < 0) a *= -1, b *= -1;
return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
if(b < 0) a *= -1, b *= -1;
return a>0 ? (a-1)/b+1 : a/b;
}
constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;
struct SegTree_beats{
const lint b_INF = 1LL << 60;
int sz;
vector<lint> MAX_val, sMAX_val, MAX_cnt;
vector<lint> min_val, smin_val, min_cnt;
vector<lint> len, sum, ladd, lval;
inline void init_node(int i, lint x){
MAX_val[i] = min_val[i] = sum[i] = x;
sMAX_val[i] = -b_INF; smin_val[i] = b_INF;
MAX_cnt[i] = min_cnt[i] = 1;
}
inline void init_empty_node(int i){
MAX_val[i] = sMAX_val[i] = -b_INF;
min_val[i] = smin_val[i] = b_INF;
MAX_cnt[i] = min_cnt[i] = 0;
}
inline void update_node_max(int i, lint x){
sum[i] += (x - MAX_val[i]) * MAX_cnt[i];
if(MAX_val[i] == min_val[i]) MAX_val[i] = min_val[i] = x;
else if(MAX_val[i] == smin_val[i]) MAX_val[i] = smin_val[i] = x;
else MAX_val[i] = x;
if(lval[i] != b_INF && lval[i] < x) lval[i] = x;
}
inline void update_node_min(int i, lint x){
sum[i] += (x - min_val[i]) * min_cnt[i];
if(min_val[i] == MAX_val[i]) min_val[i] = MAX_val[i] = x;
else if(MAX_val[i] == smin_val[i]) min_val[i] = sMAX_val[i] = x;
else min_val[i] = x;
if(lval[i] != b_INF && x < lval[i]) lval[i] = x;
}
inline void update_node_add(int i, lint x, int l, int r){
MAX_val[i] += x;
if(sMAX_val[i] != -b_INF) sMAX_val[i] += x;
min_val[i] += x;
if(smin_val[i] != b_INF) smin_val[i] += x;
sum[i] += x * (r - l);
if(lval[i] != b_INF) lval[i] += x;
else ladd[i] += x;
}
inline void update_node_set(int i, lint x, int l, int r){
MAX_val[i] = min_val[i] = x;
sMAX_val[i] = -b_INF; smin_val[i] = b_INF;
MAX_cnt[i] = min_cnt[i] = r - l;
sum[i] = x * (r - l);
lval[i] = x; ladd[i] = 0;
}
inline void push(int i, int l, int r){
if(lval[i] != b_INF){
update_node_set(i*2+1, lval[i], l, (l+r)/2);
update_node_set(i*2+2, lval[i], (l+r)/2, r);
lval[i] = b_INF;
return;
}
if(ladd[i] != 0){
update_node_add(i*2+1, ladd[i], l, (l+r)/2);
update_node_add(i*2+2, ladd[i], (l+r)/2, r);
ladd[i] = 0;
}
if(MAX_val[i] < MAX_val[i*2+1]) update_node_max(i*2+1, MAX_val[i]);
if(MAX_val[i] < MAX_val[i*2+2]) update_node_max(i*2+2, MAX_val[i]);
if(min_val[i] > min_val[i*2+1]) update_node_min(i*2+1, min_val[i]);
if(min_val[i] > min_val[i*2+2]) update_node_min(i*2+2, min_val[i]);
}
inline void pull(int i){
int s = i*2+1, t = i*2+2;
sum[i] = sum[s] + sum[t];
if(MAX_val[s] > MAX_val[t]){
MAX_val[i] = MAX_val[s];
MAX_cnt[i] = MAX_cnt[s];
sMAX_val[i] = max(sMAX_val[s], MAX_val[t]);
}
else if(MAX_val[s] < MAX_val[t]){
MAX_val[i] = MAX_val[t];
MAX_cnt[i] = MAX_cnt[t];
sMAX_val[i] = max(MAX_val[s], sMAX_val[t]);
}
else{
MAX_val[i] = MAX_val[s];
MAX_cnt[i] = MAX_cnt[s] + MAX_cnt[t];
sMAX_val[i] = max(sMAX_val[s], sMAX_val[t]);
}
if(min_val[s] < min_val[t]){
min_val[i] = min_val[s];
min_cnt[i] = min_cnt[s];
smin_val[i] = min(smin_val[s], min_val[t]);
}
else if(min_val[s] > min_val[t]){
min_val[i] = min_val[t];
min_cnt[i] = min_cnt[t];
smin_val[i] = min(min_val[s], smin_val[t]);
}
else{
min_val[i] = min_val[s];
min_cnt[i] = min_cnt[s] + min_cnt[t];
smin_val[i] = min(smin_val[s], smin_val[t]);
}
}
SegTree_beats(int sz_, lint x){
sz = 1;
while(sz < sz_) sz *= 2;
MAX_val.resize(sz*2-1); sMAX_val.resize(sz*2-1); MAX_cnt.resize(sz*2-1);
min_val.resize(sz*2-1); smin_val.resize(sz*2-1); min_cnt.resize(sz*2-1);
sum.resize(sz*2-1); ladd.resize(sz*2-1, 0); lval.resize(sz*2-1, b_INF);
rep(i, sz_) init_node(i+sz-1, x);
For(i, sz_, sz) init_empty_node(i+sz-1);
rrep(i, sz-1) pull(i);
}
SegTree_beats(int sz_, vector<lint> &a){
sz = 1;
while(sz < sz_) sz *= 2;
MAX_val.resize(sz*2-1); sMAX_val.resize(sz*2-1); MAX_cnt.resize(sz*2-1);
min_val.resize(sz*2-1); smin_val.resize(sz*2-1); min_cnt.resize(sz*2-1);
sum.resize(sz*2-1); ladd.resize(sz*2-1, 0); lval.resize(sz*2-1, b_INF);
rep(i, a.size()) init_node(i+sz-1, a[i]);
For(i, a.size(), sz) init_empty_node(i+sz-1);
rrep(i, sz-1) pull(i);
}
void update_min(int a, int b, lint x, int i=0, int l=0, int r=-1){
if(r < 0) r = sz;
if(r<=a || b<=l || MAX_val[i] <= x) return;
else if(a<=l && r<=b && sMAX_val[i] < x){
update_node_max(i, x);
}
else{
push(i, l, r);
update_min(a, b, x, i*2+1, l, (l+r)/2);
update_min(a, b, x, i*2+2, (l+r)/2, r);
pull(i);
}
}
void update_max(int a, int b, lint x, int i=0, int l=0, int r=-1){
if(r < 0) r = sz;
if(r<=a || b<=l || min_val[i] >= x) return;
else if(a<=l && r<=b && smin_val[i] > x){
update_node_min(i, x);
}
else{
push(i, l, r);
update_max(a, b, x, i*2+1, l, (l+r)/2);
update_max(a, b, x, i*2+2, (l+r)/2, r);
pull(i);
}
}
void update_add(int a, int b, lint x, int i=0, int l=0, int r=-1){
if(r < 0) r = sz;
if(r<=a || b<=l) return;
else if(a<=l && r<=b) update_node_add(i, x, l, r);
else{
push(i, l, r);
update_add(a, b, x, i*2+1, l, (l+r)/2);
update_add(a, b, x, i*2+2, (l+r)/2, r);
pull(i);
}
}
void update_set(int a, int b, lint x, int i=0, int l=0, int r=-1){
if(r < 0) r = sz;
if(r<=a || b<=l) return;
else if(a<=l && r<=b) update_node_set(i, x, l, r);
else{
push(i, l, r);
update_set(a, b, x, i*2+1, l, (l+r)/2);
update_set(a, b, x, i*2+2, (l+r)/2, r);
pull(i);
}
}
lint get_max(int a, int b, int i=0, int l=0, int r=-1){
if(r < 0) r = sz;
if(r<=a || b<=l) return -b_INF;
else if(a<=l && r<=b) return MAX_val[i];
else{
push(i, l, r);
lint vl = get_max(a, b, i*2+1, l, (l+r)/2);
lint vr = get_max(a, b, i*2+2, (l+r)/2, r);
return max(vl, vr);
}
}
lint get_min(int a, int b, int i=0, int l=0, int r=-1){
if(r < 0) r = sz;
if(r<=a || b<=l) return b_INF;
else if(a<=l && r<=b) return min_val[i];
else{
push(i, l, r);
lint vl = get_min(a, b, i*2+1, l, (l+r)/2);
lint vr = get_min(a, b, i*2+2, (l+r)/2, r);
return min(vl, vr);
}
}
lint get_sum(int a, int b, int i=0, int l=0, int r=-1){
if(r < 0) r = sz;
if(r<=a || b<=l) return 0;
else if(a<=l && r<=b) return sum[i];
else{
push(i, l, r);
lint vl = get_sum(a, b, i*2+1, l, (l+r)/2);
lint vr = get_sum(a, b, i*2+2, (l+r)/2, r);
return vl + vr;
}
}
};
int main(){
int n;
scanf("%d", &n);
int offset = 20010;
SegTree_beats st_u(2*offset, -MAX), st_d(2*offset, MAX);
int L = MAX, R = -MAX;
lint S = 0;
rep(_, n){
int xa, ya, xb, yb;
scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
xa += offset; xb += offset;
chmin(L, xa);
chmax(R, xb);
st_u.update_max(xa, xb, yb);
st_d.update_min(xa, xb, ya);
lint T = st_u.get_sum(L, R) - st_d.get_sum(L, R);
printf("%lld\n", T - S);
S = T;
}
}