Submission #619789

#	Time	Username	Problem	Language	Result	Execution time	Memory
619789		BJoozz	Building Bridges (CEOI17_building)	C++14	100 / 100	91 ms	66444 KiB

building

#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;

#define int long long
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
typedef pair < int , int > ii;
using ll = long long;
using ld = long double;
const int MAX=1e5+5,M=1e6+2,inf=1e16,mod=1e9+7;
template <class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}
void maxx(int &a,int b){if(b>a)a=b;}
void minn(int &a,int b){if(b<a)a=b;}
void PL(int &a,int b) {a+=b;if(a>=mod) a-=mod;}
int a[MAX],b[MAX];
int dp[MAX];
struct line{
    int a,b;
    line(){}
    line(int a,int b):a(a),b(b) {}
    int get(int x){return a*x+b;}
};
line ST[M*4+2];
line now;
int nx;
void upd(int id,int l,int r){
    if(l==r){
        if(now.get(l)>ST[id].get(l)) ST[id]=now;
        return;
    }
    int mid=l+r>>1;
    if(ST[id].a>now.a) swap(ST[id],now);
    if(ST[id].get(mid)<now.get(mid)){
        swap(ST[id],now);upd(id<<1,l,mid);
    }else upd(id<<1|1,mid+1,r);
}
int get(int id,int l,int r){
    if(l==r) return ST[id].get(nx);
    int mid=l+r>>1;
    if(nx<=mid) return max(ST[id].get(nx),get(id<<1,l,mid));
    else return max(ST[id].get(nx),get(id<<1|1,mid+1,r));
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("A.inp","r",stdin);//freopen("A.out","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i],b[i]+=b[i-1];
    ///dpi = dpj + Bi-1 - Bj + hi2 + hj2 -2hihj
    ///=dpj-Bj+hj2-2hj *nx
    now=line(a[1]*2,-(dp[1]-b[1]+a[1]*a[1]));
    for(int i=0;i<=M*4;i++)ST[i]=now;

    for(int i=2;i<=n;i++){
        nx=a[i];
        dp[i]=-get(1,0,M)+nx*nx+b[i-1];
        now=line(a[i]*2,-(dp[i]-b[i]+nx*nx));
        upd(1,0,M);
        //cout<<i<<' '<<dp[i]<<'\n';
    }
    cout<<dp[n];
}

Compilation message (stderr)

building.cpp: In function 'void upd(long long int, long long int, long long int)':
building.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int mid=l+r>>1;
      |             ~^~
building.cpp: In function 'long long int get(long long int, long long int, long long int)':
building.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid=l+r>>1;
      |             ~^~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40