Submission #850225

#	Time	Username	Problem	Language	Result	Execution time	Memory
850225		Tai_xiu	Building Bridges (CEOI17_building)	C++14	100 / 100	57 ms	69528 KiB

building

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100005;
const int len=1000016;
const int oo=1e18;
struct line
{
    long long a,b;
    int operator() (const int x) const {
        return a*x+b;
    }
}t[8*len];
int s[maxn],a[maxn],n;
void build (int v,int tl,int tr)
{
    t[v]={0,oo};
    if (tl==tr){
        return;
    }
    int tm=(tl+tr)>>1;
    build(v*2,tl,tm);
    build(v*2+1,tm+1,tr);
}
void update(int v, int tl,int tr,line l)
{
   if (tl==tr){
        if (t[v](tl)>l(tl))
            t[v]=l;
        return;
   }
   int tm=tl+tr>>1;
   if (l.a>t[v].a) swap(t[v],l);
   if (t[v](tm)>l(tm))
        {
            swap(t[v],l);
            update(v*2,tl,tm,l);
        }
    else update(v*2+1,tm+1,tr,l);
}
int query(int v,int tl,int tr,int val)
{
   if (tl==tr)
     return t[v](val);
    int tm=(tl+tr)>>1;
    if (val<tm)
        return min(t[v](val),query(v*2,tl,tm,val));
    return min(t[v](val),query(v*2+1,tm+1,tr,val));
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
   cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	for (int i=1;i<=n;i++){
		cin>>s[i];
		s[i]+=s[i-1];
		//cout<<s[i]<<" ";
	}
	/*
	for (int i=1;i<=n;i++)
		cout<<s[i]<<" ";
	cout<<endl;*/

	build(1,-len,len);
	update(1,-len,len,{a[1],a[1]*a[1]-s[1]});
	for (int i=2;i<n;i++){
		int x=query(1,-len,len,-2*a[i]);
		update(1,-len,len,{a[i],a[i]*a[i]-s[i]+s[i-1]+x+a[i]*a[i]});
		//cout<<(a[i]*a[i])+s[i-1]-s[i]<<'\n';
		//cout<<x<<endl;
		//cout<<x+s[i-1]+a[i]*a[i]<<" ";
	}
	cout<<query(1,-len,len,-2*a[n])+s[n-1]+a[n]*a[n];
}

Compilation message (stderr)

building.cpp: In function 'void update(long long int, long long int, long long int, line)':
building.cpp:32:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |    int tm=tl+tr>>1;
      |           ~~^~~

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