Submission #169136

#	Time	Username	Problem	Language	Result	Execution time	Memory
169136		CaroLinda	Building Bridges (CEOI17_building)	C++14	100 / 100	121 ms	66552 KiB

building

#include <bits/stdc++.h>

#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define ll long long
#define sz size()
#define pii pair<int,int>
#define all(x) x.begin(),x.end()

const int MAXN = 1e5+10 ;
const int MAX = 1e6+10, pat = 1e3+10 ;
const ll inf = 1e18+5 ;

using namespace std ;

struct Line
{

	ll a , b ;

	Line(ll a = 1 , ll b = 0) : a(a) , b(b) {}

	ll get(ll x ) 
	{
		if( a > 0 ) return inf ;
		return a*x + b ;
	}

	void print() { printf("%lld %lld\n" ,a , b ) ; }

} tree[MAX*4] ;

int n ;
ll sw[MAXN] , dp[MAXN] , h[MAXN]  ;
bool vis[MAX*4] ;

ll q(ll x) { return x*x ; }

int m(int l, int r) { return (l+r)>>1 ; }

void upd(int pos, int l, int r, Line v)
{

	if( !vis[pos] ) 
	{
		vis[pos] = true ;
		tree[pos] = v ;
		return ;
	}

	if( tree[pos].get(l) <= v.get(l) && tree[pos].get(r) <= v.get(r) ) return ;
	else if( tree[pos].get(l) > v.get(l) && tree[pos].get(r) > v.get(r) )
		return (void)(tree[pos] = v ) ;

	if( tree[pos].get(l) > v.get(l) ) swap( tree[pos] , v ) ;
	if( tree[pos].get( m(l,r) ) < v.get( m(l,r) ) ) upd( 2*pos+1, m(l,r)+1, r, v ) ;
	else
	{
		swap( tree[pos] , v ) ;
		upd( 2*pos , l , m(l,r) , v ) ;
	}

}

ll getAns(int pos, int l, int r, ll x)
{

	ll ans = tree[pos].get(x) ;
	if(l==r) return ans ;
	if( x <= m(l,r) ) return min(ans, getAns(pos*2,l,m(l,r) , x) ) ;
	return min( ans , getAns(pos*2+1,m(l,r)+1,r, x) ) ;
}

void print(int pos, int l, int r)
{
	if( l == r ) 
	{
		printf("%d %d -> " , l, r) ;
		tree[pos].print() ;
		return ;
	}
	print(pos*2,l,m(l,r)) ;
	printf("%d %d -> " , l, r) ;
		tree[pos].print() ;
	print(pos*2+1,m(l,r)+1, r) ;
}

int main()
{

	scanf("%d", &n ) ;
	lp(i,1,n+1) scanf("%lld",&h[i]) ;
	lp(i,1,n+1)
	{
		scanf("%lld", &sw[i]) ;
		sw[i] += sw[i-1] ;
	}

	upd( 1 , 0 , MAX-5 , Line(h[n]*(-2) , q(h[n]) + sw[n-1]  )  ) ;
	
	for(int i = n-1 ; i > 0 ; i-- )
	{
		
		dp[i] = getAns( 1 , 0 , MAX-5 , h[i] )  - sw[i] + q(h[i]) ;
		upd(1,0,MAX-5 , Line( h[i] * (-2) , q( h[i] ) + sw[i-1] + dp[i] )  ) ;

	}

	printf("%lld\n" , dp[1] ) ;
 
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n ) ;
  ~~~~~^~~~~~~~~~~
building.cpp:96:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  lp(i,1,n+1) scanf("%lld",&h[i]) ;
              ~~~~~^~~~~~~~~~~~~~
building.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &sw[i]) ;
   ~~~~~^~~~~~~~~~~~~~~~

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