oj.uz

Submission #397425

# Submission time Handle Problem Language Result Execution time Memory
397425 2021-05-02T07:11:28 Z Nicholas_Patrick Building Bridges (CEOI17_building) C++17
100 / 100
 104 ms 6308 KB 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

struct cht{
	struct line{
		long long m, c;
		line(long long m=0, long long c=1e18):m(m), c(c){}
		long long eval(long long x){
			return m*x+c;
		}
	};
	int n;
	vector<long long> x;
	vector<line> ch;
	cht(vector<int> init){
		sort(init.begin(), init.end());
		x.resize(n=unique(init.begin(), init.end())-init.begin());
		for(int i=n; i--;)
			x[i]=init[i];
		ch.resize(n*2-1);
	}
	void update(line y, int node, int curl, int curr){
		bool leftBetter=y.eval(x[curl])<=ch[node].eval(x[curl]),
			rightBetter=y.eval(x[curr-1])<=ch[node].eval(x[curr-1]);
		if(not leftBetter and not rightBetter)
			return;
		if(leftBetter and rightBetter){
			ch[node]=y;
			return;
		}
		int mid=curl+curr>>1;
		update(y, node+1, curl, mid);
		update(y, node+(curr-curl&~1), mid, curr);
	}
	void push_back(long long m, long long c){
		update(line(m, c), 0, 0, n);
	}
	long long query(int i, int node, int curl, int curr){
		long long ret=ch[node].eval(x[i]);
		if(curr-curl>1){
			int mid=curl+curr>>1;
			if(i<mid){
				ret=min(ret, query(i, node+1, curl, mid));
			}else{
				ret=min(ret, query(i, node+(curr-curl&~1), mid, curr));
			}
		}
		return ret;
	}
	long long eval(long long test){
		int i=lower_bound(x.begin(), x.end(), test)-x.begin();
		return query(i, 0, 0, n);
	}
};
int main(){
	int n;
	scanf("%d", &n);
	vector<int> h(n), w(n);
	for(int& i: h)
		scanf("%d", &i);
	long long sumw=0;
	for(int& i: w){
		scanf("%d", &i);
		sumw+=i;
		i=-i;
	}
	cht ch(h);
	ch.push_back(-2*h[0], (long long)h[0]*h[0]+w[0]);
	for(int i=1; i+1<n; i++){
		long long cost=ch.eval(h[i]);
		cost+=(long long)h[i]*h[i]+w[i];
		ch.push_back(-2*h[i], (long long)h[i]*h[i]+cost);
	}
	long long ans=ch.eval(h[n-1]);
	ans+=(long long)h[n-1]*h[n-1]+w[n-1]+sumw;
	printf("%lld\n", ans);
}

Compilation message

building.cpp: In member function 'void cht::update(cht::line, int, int, int)':
building.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid=curl+curr>>1;
      |           ~~~~^~~~~
building.cpp:35:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   35 |   update(y, node+(curr-curl&~1), mid, curr);
      |                   ~~~~^~~~~
building.cpp: In member function 'long long int cht::query(int, int, int, int)':
building.cpp:43:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |    int mid=curl+curr>>1;
      |            ~~~~^~~~~
building.cpp:47:37: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   47 |     ret=min(ret, query(i, node+(curr-curl&~1), mid, curr));
      |                                 ~~~~^~~~~
building.cpp: In function 'int main()':
building.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d", &i);
      |   ~~~~~^~~~~~~~~~
building.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d", &i);
      |   ~~~~~^~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 1740 KB Output is correct
2 Correct 91 ms 2720 KB Output is correct
3 Correct 89 ms 2720 KB Output is correct
4 Correct 80 ms 2384 KB Output is correct
5 Correct 77 ms 6232 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 89 ms 1740 KB Output is correct
7 Correct 91 ms 2720 KB Output is correct
8 Correct 89 ms 2720 KB Output is correct
9 Correct 80 ms 2384 KB Output is correct
10 Correct 77 ms 6232 KB Output is correct
11 Correct 100 ms 5020 KB Output is correct
12 Correct 104 ms 4896 KB Output is correct
13 Correct 54 ms 2588 KB Output is correct
14 Correct 103 ms 5060 KB Output is correct
15 Correct 80 ms 6176 KB Output is correct
16 Correct 75 ms 6308 KB Output is correct
17 Correct 28 ms 2464 KB Output is correct
18 Correct 28 ms 2460 KB Output is correct