Submission #38820861

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
template<class T, T Q=2> constexpr T inf = numeric_limits<T>::max() / Q - 1;
template<class T,class S=T>inline bool umin(T&m,S&&x){return x<m?m=x,1:0;}
template<class T,class S=T>inline bool umax(T&m,S&&x){return m<x?m=x,1:0;}
auto operator<<(ostream&o,auto&&v)->enable_if_t<!is_constructible_v<string,decltype(v)>,decltype(o<<*end(v))>{int f=0,u=&o!=&cerr;o<<"["+u;for(auto&&x:v)(f++?o<<", "+u:o)<<x;return o<<"]"+u;}
auto operator<<(ostream&o,auto&&t)->decltype(o<<get<0>(t)){int f=0,u=&o!=&cerr;o<<"<"+u;apply([&](auto&...x){(((f++?o<<", "+u:o)<<x),...);},t);return o<<">"+u;}
#ifdef BIZON
	#define rr(v...) [](auto&&...x){ cerr << boolalpha << "\e[1;38;5;68m" << #v << " "; int _=0; ((cerr<<"\e[0;38;5;61m"<<",="[!_++]<<"\e[0m "<<x),...)<<endl; }(v);
#else
	#define rr(...) ;
	#define endl '\n'
#endif
#define bb(c) begin(c), end(c)
#define ff(T, name, args...) function<T(args)> name = [&](args)->T
#define jj(v...) v; [](auto&...x){(cin>>...>>x);}(v);
#define ii(v...) int jj(v)
using ll = long long;


void run_case(const size_t ____case) { // rr(____case)
	ii(bn, n)
	vector<ll> b(bn);
	for(auto &it : b) cin >> it;
	
	vector<int> c(n);
	for(auto &it : c) cin >> it;
	
	b.push_back(1e9);
	sort(bb(b), greater{});
	
	rr(b)
	
	vector<int> p(n);
	iota(bb(p), 0);
	sort(bb(p), [&](int i, int j) { return c[i] < c[j]; });
	
	auto f = [&b](int i, ll C) {
		return (b[i] + C) * i;
	};
	
	vector<ll> ans(n);
	list<int> cur;
	vector<list<int>::iterator> iters(size(b));
	for(int i=1; i<size(b); ++i) {
		while(!empty(cur) && f(cur.back(), 0) <= f(i, 0)) cur.pop_back();
		cur.push_back(i);
		iters[i] = prev(end(cur));
	}
	
	set<pair<ll,int>> q;
	auto when = [&](int i, int j) {
		assert(i > j);
		ll pc = (j * b[j] - i * b[i]) / (i - j);
		while(f(i, pc) < f(j, pc)) ++pc;
		assert(f(i, pc) >= f(j, pc));
		if(pc) assert(f(i, pc-1) < f(j, pc-1));
		return pc;
	};
	
	for(auto it = begin(cur); next(it) != end(cur); ++it) {
		int j = *it, i = *next(it);
		q.emplace(when(i, j), i);
	}
	
	rr(cur, q)
	
	for(int k : p) {
		ll C = c[k];
		while(!empty(q) && begin(q)->first <= C) {
			auto [_, i] = *begin(q);
			q.erase(begin(q));
			auto it = iters[i];
			assert(it != begin(cur));
			auto jt = prev(it);
			if(jt != begin(cur)) {
				int j = *jt, pj = *prev(jt);
				q.erase({when(j, pj), j});
				q.emplace(when(i, pj), i);
			}
			cur.erase(jt);
		}
		ans[k] = f(cur.front(), C);
		rr(cur, C)
	}
	
	cout << ans << endl;
	
}

int main() {
	if(auto f="in.txt"; fopen(f,"r") && freopen(f,"r",stdin));
	cin.tie(0)->sync_with_stdio(0);
	
	size_t tn = 1; //cin>>tn;
	for(size_t t=1; t<=tn; ++t) run_case(t);
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp:6:27: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
    6 | auto operator<<(ostream&o,auto&&v)->enable_if_t<!is_constructible_v<string,decltype(v)>,decltype(o<<*end(v))>{int f=0,u=&o!=&cerr;o<<"["+u;for(auto&&x:v)(f++?o<<", "+u:o)<<x;return o<<"]"+u;}
      |                           ^~~~
./Main.cpp:7:27: warning: use of ‘auto’ in parameter declaration only available with ‘-fconcepts’
    7 | auto operator<<(ostream&o,auto&&t)->decltype(o<<get<0>(t)){int f=0,u=&o!=&cerr;o<<"<"+u;apply([&](auto&...x){(((f++?o<<", "+u:o)<<x),...);},t);return o<<">"+u;}
      |                           ^~~~
./Main.cpp: In function ‘void run_case(size_t)’:
./Main.cpp:45:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   45 |  for(int i=1; i<size(b); ++i) {
      |               ~^~~~~~~~
./Main.cpp:21:28: warning: unused parameter ‘____case’ [-Wunused-parameter]
   21 | void run_case(const size_t ____case) { // rr(____case)
      |               ~~~~~~~~~~~~~^~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:92:59: warning: suggest braces around empty body in an ‘if’ statement [-Wempty-body]
   92 |  if(auto f="in.txt"; fopen(f,"r") && freopen(f,"r",stdin));
      |                                                           ^

Judge Result