Submission #529168

#	Time	Username	Problem	Language	Result	Execution time	Memory
529168		FatihSolak	Building Bridges (CEOI17_building)	C++17	100 / 100	245 ms	16128 KiB

building

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40