Submission #1036644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036644		hotboy2703	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	2765 ms	708016 KiB

bodyguard

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
ll n,q;
const ll MAXN = 2827;
const ll MAX_Q = 3e6+100;
const ll INF = 1e18;
ll V[MAXN],A[MAXN],B[MAXN],C[MAXN],D[MAXN];

ll P[MAX_Q],X[MAX_Q];

ll ans[MAX_Q];
struct query{
	ll r,c,id;
};
query all[MAX_Q];
ll inter(pll x1,pll x2){
	swap(x1,x2);
	if (x1.fi==x2.fi)return (x1.se < x2.se ? -INF : INF);
	return (x2.se-x1.se)/(x1.fi-x2.fi);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	cin>>n>>q;
	for (ll i = 1;i <= n;i ++){
		cin>>C[i]>>A[i]>>B[i]>>V[i];
		D[i] = C[i] + abs(A[i]-B[i]);
	}
	for (ll i = 1;i <= q;i ++){
		cin>>P[i]>>X[i];
	}
	vector <ll> row,col;
	for (ll i = 1;i <= n;i ++){
		row.push_back(C[i]+A[i]); 
		row.push_back(D[i]+B[i]);
		col.push_back(C[i]-A[i]);
		col.push_back(D[i]-B[i]);
	}
	sort(row.begin(),row.end());
	row.resize(unique(row.begin(),row.end())-row.begin());
	sort(col.begin(),col.end());
	col.resize(unique(col.begin(),col.end())-col.begin());
	vector <vector <ll> > ar,ac,dp;
	dp=ar=ac=vector<vector <ll> > (sz(row),vector <ll>(sz(col)));
	for (ll i = 1;i <= n;i ++){
		if (A[i] > B[i]){
			ll x = lower_bound(row.begin(),row.end(),C[i]+A[i])-row.begin();
			for (ll j = 0;j < sz(col);j ++){
				if (C[i] - A[i] < col[j] && D[i] - B[i] >= col[j]){
					ar[x][j] = max(V[i],ar[x][j]);
				}
			}
		}
		else{
			ll y = lower_bound(col.begin(),col.end(),C[i]-A[i])-col.begin();
			for (ll j = 0;j < sz(row);j ++){
				if (C[i] + A[i] < row[j] && row[j] <= D[i] + B[i]){
					ac[j][y] = max(ac[j][y],V[i]);
				}
			}
		}
	}
	for (ll i = sz(row)-1; i >= 0; i --){
		for (ll j = sz(col)-1; j >= 0; j --){
			if (i)dp[i-1][j] = max(dp[i-1][j],dp[i][j] + ac[i][j] * (row[i] - row[i-1]));
			if (j)dp[i][j-1] = max(dp[i][j-1],dp[i][j] + ar[i][j] * (col[j] - col[j-1]));
		}
	}
	// for (ll i = 0;i < sz(row);i ++){
	// 	for (ll j = 0;j < sz(col);j ++){
	// 		cout<<"DP "<<row[i]<<' '<<col[j]<<" : "<<dp[i][j]<<endl;
	// 	}
	// }
	for (ll i = 1;i <= q;i ++){
		all[i] = {P[i]+X[i],P[i]-X[i],i};
		// cout<<P[i]+X[i]<<' '<<P[i]-X[i]<<endl;
	}
	// cout<<row[5]<<' '<<col[3]<<' '<<ar[5][3]<<' '<<ac[5][3]<<endl;
	sort(all+1,all+1+q,[](query a1,query a2){return a1.r < a2.r;});
	for (ll i = 0,ptr = 1;i < sz(row);i ++){
		vector <query> cur;
		while (ptr <= q && all[ptr].r <= row[i]){cur.push_back(all[ptr]);ptr++;}
		sort(cur.begin(),cur.end(),[](query a1,query a2){return a1.c > a2.c;});
		ll ptr_cur = 0;
		while (ptr_cur < sz(cur) && cur[ptr_cur].c > col.back())ptr_cur++;
		vector <pll> hull;
		for (ll j = sz(col)-1;j >= 0;j --){
			ll tmp = j?col[j-1]:-INF;
			while (sz(hull) && hull.back().fi <= ac[i][j] && hull.back().se <= dp[i][j])hull.pop_back();
			while (sz(hull) >= 2 && inter(hull[sz(hull)-2],hull[sz(hull)-1]) <= inter(hull[sz(hull)-1],MP(ac[i][j],dp[i][j])))hull.pop_back();
			hull.push_back(MP(ac[i][j],dp[i][j]));
			while (ptr_cur < sz(cur) && cur[ptr_cur].r <= row[i] && cur[ptr_cur].c > tmp && cur[ptr_cur].c <= col[j]){
				// if (all[ptr].id == 1){cout<<row[i]<<' '<<col[j]<<endl;for (auto x:hull)cout<<x.fi<<' '<<x.se<<endl;}
				ll x = row[i] - cur[ptr_cur].r;
				ll l = 0,r = sz(hull) - 1;
				while (l <= r){
					ll mid = (l + r) >> 1;
					if (mid == 0 || hull[mid].fi * x + hull[mid].se > hull[mid-1].fi * x + hull[mid-1].se) l = mid + 1;
					else r = mid - 1;
				}
				ans[cur[ptr_cur].id] = max(ans[cur[ptr_cur].id],hull[r].fi * x + hull[r].se);
				ptr_cur++;
			}
		}
	}

	sort(all+1,all+1+q,[](query a1,query a2){return a1.c<a2.c;});
	// for (ll i = 1;i <= q;i ++){
	// 	cout<<all[i].r<<' '<<all[i].c<<' '<<all[i].id<<endl;
	// }
	// cout<<ar[0][0]<<' '<<ans[1]<<endl;
	for (ll i = 0,ptr = 1;i < sz(col);i ++){
		vector <query> cur;
		while (ptr <= q && all[ptr].c <= col[i]){cur.push_back(all[ptr]);ptr++;}
		sort(cur.begin(),cur.end(),[](query a1,query a2){return a1.r > a2.r;});
		ll ptr_cur = 0;
		while (ptr_cur < sz(cur) && cur[ptr_cur].r > row.back())ptr_cur++;
		vector <pll> hull;
		for (ll j = sz(row)-1;j >= 0;j --){
			ll tmp = j?row[j-1]:-INF;
			while (sz(hull) && hull.back().fi <= ar[j][i] && hull.back().se <= dp[j][i])hull.pop_back();
			while (sz(hull) >= 2 && inter(hull[sz(hull)-2],hull[sz(hull)-1]) <= inter(hull[sz(hull)-1],MP(ar[j][i],dp[j][i])))hull.pop_back();
			hull.push_back(MP(ar[j][i],dp[j][i]));
			while (ptr_cur < sz(cur) && cur[ptr_cur].c <= col[i] && cur[ptr_cur].r > tmp && cur[ptr_cur].r <= row[j]){
				ll x = col[i] - cur[ptr_cur].c;
				ll l = 0,r = sz(hull) - 1;
				while (l <= r){
					ll mid = (l + r) >> 1;
					if (mid == 0 || hull[mid].fi * x + hull[mid].se > hull[mid-1].fi * x + hull[mid-1].se) l = mid + 1;
					else r = mid - 1;
				}
				ans[cur[ptr_cur].id] = max(ans[cur[ptr_cur].id],hull[r].fi * x + hull[r].se);
				// cout<<"WAT "<<ptr_cur<<' '<<i<<' '<<j<<endl;
				ptr_cur++;
			}
		}
	}
	for (ll i = 1;i <= q;i ++)cout<<ans[i]/2<<'\n';
}

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