結果

問題 No.1074 増殖
ユーザー Ricky_ponRicky_pon
提出日時 2020-06-05 23:33:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 235 ms / 2,000 ms
コード長 8,780 bytes
コンパイル時間 2,361 ms
コンパイル使用メモリ 210,840 KB
実行使用メモリ 21,812 KB
最終ジャッジ日時 2023-08-22 18:10:31
合計ジャッジ時間 4,595 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 17 ms
21,516 KB
testcase_01 AC 16 ms
21,504 KB
testcase_02 AC 16 ms
21,596 KB
testcase_03 AC 16 ms
21,812 KB
testcase_04 AC 16 ms
21,568 KB
testcase_05 AC 16 ms
21,660 KB
testcase_06 AC 151 ms
21,568 KB
testcase_07 AC 116 ms
21,632 KB
testcase_08 AC 131 ms
21,608 KB
testcase_09 AC 235 ms
21,572 KB
testcase_10 AC 146 ms
21,540 KB
testcase_11 AC 81 ms
21,664 KB
testcase_12 AC 80 ms
21,572 KB
testcase_13 AC 159 ms
21,568 KB
testcase_14 AC 159 ms
21,540 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
    }
}
0