oj.uz

Submission #544659

# Submission time Handle Problem Language Result Execution time Memory
544659 2022-04-02T14:16:47 Z pokmui9909 수족관 1 (KOI13_aqua1) C++17
100 / 100
 5 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
#define x first
#define y second
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[5005];
Data V[5005];
ll ans = 0;
 
void dnc(ll l, ll r, ll s){
    if(l > r) return;
    ll mn = 1e9, idx = 0;
    ll ok = 0;
    for(int i = l; i <= r; i++){
        if(mn > V[i].w) mn = V[i].w, idx = i;
        if(V[i].t == 1) ok = 1;
    }
    if(ok){
        ans -= (mn - s) * (V[r].r - V[l].l);
        dnc(l, idx - 1, mn);
        dnc(idx + 1, r, mn);
    } else {
        return;
    }
}
 
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++;
        }
    }
    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;
    }
    dnc(1, M, 0);
    cout << ans;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 420 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct