oj.uz

Submission #544660

# Submission time Handle Problem Language Result Execution time Memory
544660 2022-04-02T14:16:57 Z pokmui9909 수족관 3 (KOI13_aqua3) C++17
100 / 100
 163 ms 44708 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second
const ll INF = 1e15;
const ll S = (1 << 18);
struct MinSeg{
    pair<ll, ll> T[2 * S] = {};
    MinSeg(){fill(T, T + 2 * S, make_pair(INF, INF)); }
    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;
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];
priority_queue<ll> PQ;

ll dnc(ll l, ll r, ll s){
    if(l > r) return 0;
    ll mn = ST.query(l, r).first, idx = ST.query(l, r).second;
    ll v = (mn - s) * (V[r].r - V[l].l);
    ll p = dnc(l, idx - 1, mn);
    ll q = dnc(idx + 1, r, mn);
    PQ.push(min(p, q));
    return max(p, q) + v;
}

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};
            M++;
        }
    }
    cin >> K;
    for(int i = 1; i <= M; i++){
        ST.update(i, {V[i].w, i});
    }
    PQ.push(dnc(1, M, 0));
    ll ans = 0;
    while(!PQ.empty() && K--){
        ans += PQ.top();
        PQ.pop();
    }
    cout << ans;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8532 KB Output is correct
2 Correct 5 ms 8544 KB Output is correct
3 Correct 5 ms 8532 KB Output is correct
4 Correct 5 ms 8548 KB Output is correct
5 Correct 5 ms 8552 KB Output is correct
6 Correct 5 ms 8660 KB Output is correct
7 Correct 5 ms 8532 KB Output is correct
8 Correct 5 ms 8532 KB Output is correct
9 Correct 5 ms 8532 KB Output is correct
10 Correct 5 ms 8548 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8660 KB Output is correct
2 Correct 8 ms 8652 KB Output is correct
3 Correct 7 ms 8812 KB Output is correct
4 Correct 6 ms 8808 KB Output is correct
5 Correct 7 ms 8788 KB Output is correct
6 Correct 9 ms 9072 KB Output is correct
7 Correct 7 ms 8916 KB Output is correct
8 Correct 7 ms 8916 KB Output is correct
9 Correct 7 ms 8804 KB Output is correct
10 Correct 6 ms 8760 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 22948 KB Output is correct
2 Correct 112 ms 22860 KB Output is correct
3 Correct 136 ms 29640 KB Output is correct
4 Correct 136 ms 29732 KB Output is correct
5 Correct 147 ms 29656 KB Output is correct
6 Correct 152 ms 44588 KB Output is correct
7 Correct 142 ms 35260 KB Output is correct
8 Correct 152 ms 35316 KB Output is correct
9 Correct 134 ms 25932 KB Output is correct
10 Correct 128 ms 25924 KB Output is correct
11 Correct 163 ms 44708 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 22988 KB Output is correct
2 Correct 108 ms 22996 KB Output is correct
3 Correct 143 ms 29620 KB Output is correct
4 Correct 136 ms 29596 KB Output is correct
5 Correct 136 ms 29520 KB Output is correct
6 Correct 158 ms 44668 KB Output is correct
7 Correct 142 ms 35332 KB Output is correct
8 Correct 151 ms 35260 KB Output is correct
9 Correct 132 ms 25956 KB Output is correct
10 Correct 124 ms 25888 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 22952 KB Output is correct
2 Correct 112 ms 22892 KB Output is correct
3 Correct 141 ms 29592 KB Output is correct
4 Correct 145 ms 29588 KB Output is correct
5 Correct 146 ms 29632 KB Output is correct
6 Correct 148 ms 35284 KB Output is correct
7 Correct 150 ms 35288 KB Output is correct
8 Correct 126 ms 25836 KB Output is correct
9 Correct 131 ms 25924 KB Output is correct