Submission #1036577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036577		hotboy2703	Bodyguard (JOI21_bodyguard)	C++17	28 / 100	2029 ms	2097152 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]);
	}
	for (ll i = 1;i <= q;i ++){
		row.push_back(P[i]+X[i]); 
		col.push_back(P[i]-X[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 = 1;i <= q;i ++){
		cout<<dp[lower_bound(row.begin(),row.end(),P[i]+X[i])-row.begin()][lower_bound(col.begin(),col.end(),P[i]-X[i])-col.begin()]/2<<'\n';
	}
	// 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;
	// 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: 0 / 20
• Subtask 5: 0 / 52