結果

問題 No.1074 増殖
ユーザー gyouzasushigyouzasushi
提出日時 2020-06-06 20:02:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 4,000 bytes
コンパイル時間 1,975 ms
コンパイル使用メモリ 200,724 KB
実行使用メモリ 9,764 KB
最終ジャッジ日時 2023-08-25 01:50:35
合計ジャッジ時間 5,814 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,380 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (int i = 0; i < sz(v); i++) {
        os << v[i];
        if (i < sz(v) - 1) os << " ";
    }
    return os;
}
template <typename T, typename E>
struct LazySegmentTree {
    using F = function<T(T, T)>;
    using G = function<T(T, E)>;
    using H = function<E(E, E)>;
    int sn, hei;
    F f;
    G g;
    H h;
    T ti;
    E ei;
    vector<T> node;
    vector<E> lazy;
    LazySegmentTree(const vector<T>& v, F f, G g, H h, T ti, E ei)
        : f(f), g(g), h(h), ti(ti), ei(ei) {
        int n = v.size();
        sn = 1, hei = 0;
        while (sn < n) {
            sn <<= 1;
            hei++;
        }
        node.assign(2 * sn, ti);
        lazy.assign(2 * sn, ei);
        for (int i = 0; i < n; i++) {
            node[sn + i] = v[i];
        }
        for (int i = sn - 1; i > 0; i--) {
            node[i] = f(node[(i << 1) | 0], node[(i << 1) | 1]);
        }
    }
    inline T reflect(int k) {
        return lazy[k] == ei ? node[k] : g(node[k], lazy[k]);
    }
    inline void propagate(int k) {
        if (lazy[k] == ei) return;
        lazy[(k << 1) | 0] = h(lazy[(k << 1) | 0], lazy[k]);
        lazy[(k << 1) | 1] = h(lazy[(k << 1) | 1], lazy[k]);
        node[k] = reflect(k);
        lazy[k] = ei;
    }
    inline void thrust(int k) {
        for (int i = hei; i > 0; i--) {
            propagate(k >> i);
        }
    }
    inline void recalc(int k) {
        while (k >>= 1) {
            node[k] = f(reflect((k << 1) | 0), reflect((k << 1) | 1));
        }
    }
    void update(int a, int b, E x) {
        if (a >= b) return;
        thrust(a += sn);
        thrust(b += sn - 1);
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                lazy[l] = h(lazy[l], x);
                l++;
            }
            if (r & 1) {
                r--;
                lazy[r] = h(lazy[r], x);
            }
        }
        recalc(a);
        recalc(b);
    }
    void set_val(int a, T x) {
        thrust(a += sn);
        node[a] = x;
        lazy[a] = ei;
        recalc(a);
    }
    T query(int a, int b) {
        if (a >= b) return ti;
        thrust(a += sn);
        thrust(b += sn - 1);
        T vl = ti, vr = ti;
        for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                vl = f(vl, reflect(l));
                l++;
            }
            if (r & 1) {
                r--;
                vr = f(reflect(r), vr);
            }
        }
        return f(vl, vr);
    }
};
const int geta = 20000;
int main() {
    int n;
    cin >> n;
    vector<ll> xa(n), ya(n), xb(n), yb(n);
    rep(i, n) cin >> xa[i] >> ya[i] >> xb[i] >> yb[i];

    vector<ll> v1(40400), v2(40400);
    for (int i = 0; i < n; i++) {
        int l = xa[i] + geta;
        int r = xb[i] + geta;
        ll ans = 0;
        for (int j = l; j < r; j++) {
            ans += max(0ll, yb[i] - v1[j]);
            chmax(v1[j], yb[i]);
            ans += max(0ll, -ya[i] - v2[j]);
            chmax(v2[j], -ya[i]);
        }
        cout << ans << endl;
    }
}
0