Submission #523878

#	Time	Username	Problem	Language	Result	Execution time	Memory
523878		amunduzbaev	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	6988 ms	515892 KiB

bodyguard

#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

struct Line {
	mutable int k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(int x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const int inf = LLONG_MAX;
	int div(int a, int b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(int k, int m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	int query(int x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

const int N = 5605;
const int Q = 3e6 + 5;
const int INF = 2e9 + 5;
int x[Q], y[Q], res[Q];
int a[N], t[N], t2[N], b[N], c[N];
int up[N][N], ri[N][N], dp[N][N];
LineContainer cht[N];
vector<int> tx, ty;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	auto add = [&](int x, int y){
		tx.push_back(x);
		ty.push_back(y);
	};
	
	int n, q; cin>>n>>q;
	vector<int> a(n), b(n), c(n), t(n), t2(n);
	for(int i=0;i<n;i++){
		cin>>t[i]>>a[i]>>b[i]>>c[i];
		t2[i] = t[i] + abs(a[i] - b[i]);
		add(t[i] + a[i], t[i] - a[i]);
		add(t2[i] + b[i], t2[i] - b[i]);
	}
	
	tx.push_back(INF), tx.push_back(-INF);
	ty.push_back(INF), ty.push_back(-INF);
	sort(tx.begin(), tx.end());
	sort(ty.begin(), ty.end());
	tx.erase(unique(tx.begin(), tx.end()), tx.end());
	ty.erase(unique(ty.begin(), ty.end()), ty.end());
	auto get = [&](int x, int y) -> ar<int, 2>{
		int i = lower_bound(tx.begin(), tx.end(), x) - tx.begin(), 
		j = lower_bound(ty.begin(), ty.end(), y) - ty.begin();
		return {i, j};
	};
	
	for(int i=0;i<n;i++){
		ar<int, 2> l = get(t[i] + a[i], t[i] - a[i]), 
		r = get(t2[i] + b[i], t2[i] - b[i]);
		if(l > r) swap(l, r);
		
		if(l[0] == r[0]){
			for(int j=l[1];j<r[1];j++){
				up[l[0]][j] = max(up[l[0]][j], c[i]);
			}
		} else {
			for(int j=l[0];j<r[0];j++){
				ri[j][l[1]] = max(ri[j][l[1]], c[i]);
			}
		}
	}
	
	for(int i=(int)tx.size()-2;~i;i--){
		for(int j=(int)ty.size()-2;~j;j--){
			dp[i][j] = max(dp[i+1][j] + ri[i][j] * (tx[i+1] - tx[i]),
			dp[i][j+1] + up[i][j] * (ty[j+1] - ty[j]));
		}
	}
	
	vector<int> p(q);
	for(int i=0;i<q;i++){
		int T, P; cin>>T>>P;
		x[i] = T + P, y[i] = T - P;
		p[i] = i;
		auto n = get(x[i], y[i]);
		res[i] = dp[n[0]][n[1]];
		//~ for(int j=n[0];j<(int)tx.size();j++){
			//~ res = max(res, dp[j][n[1]] + up[j][n[1]-1] * (ty[n[1]] - y));
		//~ } for(int j=n[1];j<(int)ty.size();j++){
			//~ res = max(res, dp[n[0]][j] + ri[n[0]-1][j] * (tx[n[0]] - x));
		//~ }
		//~ cout<<res / 2<<"\n";
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (x[i] > x[j]);
	});
	
	int j = tx.size() - 1;
	for(auto i : p){
		while(tx[j] >= x[i]){
			for(int l=1;l<(int)ty.size();l++){
				//~ dp[j][l] + up[j][l-1] * ty[l]
				//~ -up[j][l-1]
				cht[l].add(-up[j][l-1], dp[j][l] + up[j][l-1] * ty[l]);
			} j--;
		}
		auto n = get(x[i], y[i]);
		res[i] = max(res[i], cht[n[1]].query(y[i]));
	}
	
	for(int i=0;i<N;i++) cht[i].clear();
	sort(p.begin(), p.end(), [&](int i, int j){
		return (y[i] > y[j]);
	}); 
	j = (int)ty.size() - 1;
	for(auto i : p){
		while(ty[j] >= y[i]){
			for(int l=1;l<(int)tx.size();l++){
				//~ dp[l][j] + up[l-1][j] * tx[l]
				//~ -up[l-1][j] * y
				cht[l].add(-ri[l-1][j], dp[l][j] + ri[l-1][j] * tx[l]);
			} j--;
		}
		
		auto n = get(x[i], y[i]);
		res[i] = max(res[i], cht[n[0]].query(x[i]));
	}
	
	for(int i=0;i<q;i++) cout<<res[i] / 2<<"\n";
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 52 / 52