oj.uz

Submission #529199

# Submission time Handle Problem Language Result Execution time Memory
529199 2022-02-22T11:45:56 Z FatihSolak Building Bridges (CEOI17_building) C++17
100 / 100
 243 ms 15956 KB 
#include <bits/stdc++.h>
#define N 100005
using namespace std;
long long h[N],w[N];
long long dp[N];
set<pair<pair<int,int>,pair<long long,long long>>> s;
set<pair<pair<long long,long long>,pair<int,int>>> p;
long long get(int x){
    auto a = *prev(s.lower_bound({{x+1,0},{0,0}}));
    return a.second.second * x + a.second.first;
}
long long intersect(long long a,long long b,long long c,long long d){
    return (d - b + a - c - 1)/(a - c);
}
long long intersect2(long long a,long long b,long long c,long long d){
    if(a - c >= 0)return 1e9;
    return (d - b)/(a - c);
}
void add(long long a,long long b){
    int l = 1e6 +5, r = 0;
    auto it = p.lower_bound({{b,-1e18},{-1e18,-1e18}});
    if(it == p.end())l = 0;
    while(it != p.end()){
        if(it->first.second >= a)break;
        long long point = intersect(a,b,it->first.second,it->first.first);
        if(point > it->second.second)break;
        l = min((long long)l,max(point,(long long)it->second.first));
        r = max(r,it->second.second);
        if(point > it->second.first)break;
        it = next(it);
    }    
    it = p.lower_bound({{b,-1e18},{-1e18,-1e18}});
    if(it == p.begin())r = 1e6;
    while(it != p.begin()){
        it = prev(it);
        long long point = intersect2(a,b,it->first.second,it->first.first);
        if(point < it->second.first)break;
        r = max((long long)r,min(point,(long long)it->second.second));
        l = min(l,it->second.first);
        if(point < it->second.second)break;
    }
    if(l > r){
        return;
    }
    if(s.lower_bound({{l,-1e18},{-1e18,-1e18}}) != s.begin()){
        auto x = *prev(s.lower_bound({{l,-1e18},{-1e18,-1e18}})); 
        if(x.first.second != l-1){
            s.erase(x);
            p.erase({x.second,x.first});
            if(x.first.second > r){
                int tmp = x.first.first;
                x.first.first = r+1;
                s.insert(x);
                p.insert({x.second,x.first});
                x.first.first = tmp;    
            }
            x.first.second = l-1;
            s.insert(x);
            p.insert({x.second,x.first});
        }
    }
    if(s.lower_bound({{r+1,-1e18},{-1e18,-1e18}}) != s.begin()){
        auto x = *prev(s.lower_bound({{r+1,-1e18},{-1e18,-1e18}})); 
        if(x.first.second > r){
            s.erase(x);
            p.erase({x.second,x.first});
            x.first.first = r+1;
            s.insert(x);
            p.insert({x.second,x.first});
        }
    }
    while(s.lower_bound({{l,-1e18},{-1e18,-1e18}}) != s.end()){
        auto x = *s.lower_bound({{l,-1e18},{-1e18,-1e18}});
        if(x.first.first <= r){
            s.erase(x);
            p.erase({x.second,x.first});
        }
        else break;
    }
    s.insert({{l,r},{b,a}});
    p.insert({{b,a},{l,r}}); 
}
void solve(){
    int n;
    cin >> n;
    long long sum = 0;
    for(int i=1;i<=n;i++){
        cin >> h[i];
    }
    for(int i=1;i<=n;i++){
        cin >> w[i];
        sum += w[i];
    }
    dp[1] = sum - w[1];
    s.insert({{0,1e6},{-(dp[1] + h[1] * h[1]),2*h[1]}});
    p.insert({{-(dp[1] + h[1] * h[1]),2*h[1]},{0,1e6}});
    for(int i=2;i<=n;i++){
        dp[i] = -get(h[i]) + h[i]*h[i] - w[i];
        add(2*h[i],-(dp[i] + h[i]*h[i]));
    }
    cout << dp[n];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0 * clock() / CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 3816 KB Output is correct
2 Correct 206 ms 3808 KB Output is correct
3 Correct 243 ms 3820 KB Output is correct
4 Correct 189 ms 3596 KB Output is correct
5 Correct 160 ms 5892 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 202 ms 3816 KB Output is correct
7 Correct 206 ms 3808 KB Output is correct
8 Correct 243 ms 3820 KB Output is correct
9 Correct 189 ms 3596 KB Output is correct
10 Correct 160 ms 5892 KB Output is correct
11 Correct 166 ms 3876 KB Output is correct
12 Correct 213 ms 3784 KB Output is correct
13 Correct 79 ms 3668 KB Output is correct
14 Correct 197 ms 3884 KB Output is correct
15 Correct 227 ms 15956 KB Output is correct
16 Correct 167 ms 5944 KB Output is correct
17 Correct 23 ms 3624 KB Output is correct
18 Correct 17 ms 3620 KB Output is correct