Submission #544667

#	Time	Username	Problem	Language	Result	Execution time	Memory
544667		pokmui9909	수족관 2 (KOI13_aqua2)	C++17	100 / 100	247 ms	37488 KiB

aqua2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
 
#define x first
#define y second
const ll INF = 1e15;
const ll S = (1 << 18);
struct MinSeg{
    pair<ll, ll> T[2 * S] = {};
    MinSeg(pair<ll, ll> z){fill(T, T + 2 * S, z); }
    void update(ll k, pair<ll, ll> v) { update(1, 1, S, k, v); }
    pair<ll, ll> query(ll l, ll r) { return query(1, 1, S, l, r); }

    void update(ll node, ll s, ll e, ll k, pair<ll, ll> v){
        if(s == e){
            T[node] = min(T[node], v);
            return;
        }
        ll lch = 2 * node, rch = 2 * node + 1, m = (s + e) / 2;
        if(k <= m) update(lch, s, m, k, v);
        else update(rch, m + 1, e, k, v);
        T[node] = min(T[lch], T[rch]);
    }
    pair<ll, ll> query(ll node, ll s, ll e, ll l, ll r){
        if(r < s || e < l) return {INF, INF};
        if(l <= s && e <= r) return T[node];
        ll lch = 2 * node, rch = 2 * node + 1, m = (s + e) / 2;
        pair<ll, ll> x = query(lch, s, m, l, r);
        pair<ll, ll> y = query(rch, m + 1, e, l, r);
        return min(x, y);
    }
};
MinSeg ST(make_pair(INF, INF));
struct Data{
    ll l, r, w, t;
    bool operator < (const Data &t) const{
        if(l != t.l) return l < t.l;
        else return r < t.r;
    }
};
ll N, K, M;
pair<ll, ll> P[300005];
Data V[300005];
ll ps[300005];
ll ans = 0;
ll hole(ll l, ll r){
    return ps[r] - ps[l - 1];
}
lf dnc(ll l, ll r, ll s){
    if(l > r) return 0;
    ll mn = ST.query(l, r).x, idx = ST.query(l, r).y;
    ll cnt = hole(l, r);
    if(cnt){
        ll v = (mn - s) * (V[r].r - V[l].l);
        ans -= v;
        lf p = dnc(l, idx - 1, mn);
        lf q = dnc(idx + 1, r, mn);
        return max(p, q) + (long double)v / cnt;
    } else {
        return 0;
    }
}
 
int main(){
    cin.tie(0) -> sync_with_stdio(false);
 
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> P[i].x >> P[i].y;
        if(i % 2 == 1 && i != 1){
            V[i / 2] = {P[i - 1].x, P[i].x, P[i].y, 0};
            ans += (P[i].y) * (P[i].x - P[i - 1].x);
            M++;
        }
    }
    for(int i = 1; i <= M; i++){
        ST.update(i, {V[i].w, i});
    }
    cin >> K;
    for(int i = 1; i <= K; i++){
        ll a, b, c, d; cin >> a >> b >> c >> d;
        Data t = {a, c, b};
        ll idx = lower_bound(V + 1, V + M + 1, t) - V;
        V[idx].t = 1;
    }
    for(int i = 1; i <= M; i++) ps[i] = ps[i - 1] + V[i].t;
    cout << fixed;
    cout.precision(2);
    cout << dnc(1, M, 0) << '\n';
    cout.precision(0);
    cout << ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 35 / 35
• Subtask 4: 31 / 31