oj.uz

Submission #529168

# Submission time Handle Problem Language Result Execution time Memory
529168 2022-02-22T10:42:34 Z FatihSolak Building Bridges (CEOI17_building) C++17
100 / 100
 245 ms 16128 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);
}
//int num = 0;
void add(long long a,long long b){
    //cout << a << " " << b << endl;
    int l = 1e6, r = 0;
    auto it = p.lower_bound({{b,-1e18},{-1e18,-1e18}});
    /*
    int mini = 1e6,maxi = 0;
    for(int i=0;i<=1e6;i++){
        if(get(i) <= a*i + b){
            mini = min(mini,i);
            maxi = max(maxi,i);
        }
    }*/
    if(it == p.end())l = 0;
    while(it != p.end()){
        /*
        if(num == 60){
            cout << it->second.first << " " << it->second.second << endl;
        }*/
        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));
        if(r == 0)
        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;
    //cout << l << endl;
    while(it != p.begin()){
        it = prev(it);
        long long point = intersect2(a,b,it->first.second,it->first.first);
        //cout << point << endl;
        if(point < it->second.first)break;
        r = max((long long)r,min(point,(long long)it->second.second));
        if(l == 1e6){
            l = min(l,it->second.first);
        }
        if(point < it->second.second)break;
    }
    /*
    if(mini != l || maxi != r){
        cout << mini << " " << maxi <<endl;
        cout << l << " " << r << endl;
        exit(0);
    }*/
    //l = mini,r = maxi;
    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}}); 
    /*
    for(auto u:s){
        cout << u.first.first << " " << u.first.second << endl;
    }
    cout << endl;*/
}
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];
    //cout << -(dp[1] + h[1] * h[1]) << endl;
    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++){
        //num = i;
        //cout << i << endl;
        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 320 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 328 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 212 ms 3964 KB Output is correct
2 Correct 210 ms 3772 KB Output is correct
3 Correct 199 ms 3752 KB Output is correct
4 Correct 219 ms 3496 KB Output is correct
5 Correct 157 ms 5856 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 212 ms 3964 KB Output is correct
7 Correct 210 ms 3772 KB Output is correct
8 Correct 199 ms 3752 KB Output is correct
9 Correct 219 ms 3496 KB Output is correct
10 Correct 157 ms 5856 KB Output is correct
11 Correct 168 ms 3780 KB Output is correct
12 Correct 245 ms 3772 KB Output is correct
13 Correct 79 ms 3652 KB Output is correct
14 Correct 195 ms 3876 KB Output is correct
15 Correct 244 ms 16128 KB Output is correct
16 Correct 160 ms 5868 KB Output is correct
17 Correct 19 ms 3652 KB Output is correct
18 Correct 46 ms 3648 KB Output is correct