oj.uz

Submission #899461

# Submission time Handle Problem Language Result Execution time Memory
899461 2024-01-06T08:52:03 Z dsyz Building Bridges (CEOI17_building) C++17
100 / 100
 51 ms 19540 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
ll N;
ll H[MAXN], W[MAXN], psum[MAXN], dp[MAXN];
struct node {
	ll s,e,m;
	bool reset;
	pair<ll,ll> line;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) >> 1; //Note that m = (s + e) / 2 will not work
		line = {0,1e18};
		reset = 0;
		l = nullptr, r = nullptr;
	}
	ll f(pair<ll,ll> line,ll x){
		return line.first * x + line.second;
	}
	void update(pair<ll,ll> nval){
		value();
		bool lt = f(nval,s) < f(line,s);
		bool mid = f(nval,m) < f(line,m);
		if(mid) swap(nval,line);
		if(s == e) return;
		if(lt == mid){
			if(r == nullptr) r = new node(m + 1,e);
			r -> update(nval);
		}else{
			if(l == nullptr) l = new node(s,m);
			l -> update(nval);
		}
	}
	ll rmq(ll x){
		value();
		if(s == e) return f(line,x);		
		if(x > m){
			ll RR = 1e18; //make sure to calculate RR inside the “x > m” if statement, if you do it outside the if statement, you might TLE
			if(r != nullptr) RR = r -> rmq(x);
			return min(f(line,x),RR);
		}else{
			ll LL = 1e18; 
			if(l != nullptr) LL = l -> rmq(x);		
			return min(f(line,x),LL);
		}
	}
	void value() {
		//this value() function is generally for codeforces problems with multiple testcases
		//so need to reset for each testcase to save space
		if(!reset) return;
		line = {0,1e18};
		if(s != e){
			if(l != nullptr) l -> reset = 1;
			if(r != nullptr) r -> reset = 1;
		}
		reset = 0;
	}
} *lichao;
//this is the minimum y lichao tree
//for maximum lichao tree, need to change all the
//min() to max() and 1e18 to -1e18 and "<" to ">" in update function
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin>>N;
	lichao = new node(-1e9,1e9);
	for(ll i = 1;i <= N;i++){
		cin>>H[i];
	}
	for(ll i = 1;i <= N;i++){
		cin>>W[i];
	}
	for(ll i = 1;i <= N;i++){
		psum[i] = psum[i - 1] + W[i];
	}
	dp[1] = 0;
	lichao -> update({-2 * H[1],(H[1] * H[1]) - psum[1] + dp[1]});
	for(ll i = 2;i <= N;i++){
		dp[i] = (H[i] * H[i]) + psum[i - 1] + lichao -> rmq(H[i]);
		lichao -> update({-2 * H[i],(H[i] * H[i]) - psum[i] + dp[i]});
	}
	cout<<dp[N]<<'\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2516 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5496 KB Output is correct
2 Correct 43 ms 5460 KB Output is correct
3 Correct 43 ms 5432 KB Output is correct
4 Correct 40 ms 4636 KB Output is correct
5 Correct 34 ms 11868 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2516 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 44 ms 5496 KB Output is correct
7 Correct 43 ms 5460 KB Output is correct
8 Correct 43 ms 5432 KB Output is correct
9 Correct 40 ms 4636 KB Output is correct
10 Correct 34 ms 11868 KB Output is correct
11 Correct 51 ms 6544 KB Output is correct
12 Correct 46 ms 7324 KB Output is correct
13 Correct 34 ms 4956 KB Output is correct
14 Correct 50 ms 7764 KB Output is correct
15 Correct 41 ms 19540 KB Output is correct
16 Correct 33 ms 11868 KB Output is correct
17 Correct 28 ms 4444 KB Output is correct
18 Correct 27 ms 4476 KB Output is correct