#663997 (C++14) No.1074 増殖

提出ソース
結果

問題	No.1074 増殖
ユーザー	rokahikou1
提出日時	2021-06-05 12:47:53
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	278 ms / 2,000 ms
コード長	13,095 bytes
コンパイル時間	2,232 ms
コンパイル使用メモリ	182,904 KB
実行使用メモリ	24,192 KB
最終ジャッジ日時	2024-05-01 07:24:53
合計ジャッジ時間	4,743 ms
ジャッジサーバーID （参考情報）	judge2 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	19 ms 24,064 KB
testcase_01	AC	20 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	19 ms 24,064 KB
testcase_06	AC	117 ms 24,064 KB
testcase_07	AC	122 ms 24,192 KB
testcase_08	AC	143 ms 24,064 KB
testcase_09	AC	278 ms 24,064 KB
testcase_10	AC	118 ms 24,064 KB
testcase_11	AC	76 ms 24,064 KB
testcase_12	AC	76 ms 24,064 KB
testcase_13	AC	173 ms 24,064 KB
testcase_14	AC	171 ms 24,064 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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;
    }
}
yukicoder

結果

テストケース

ソースコード
