oj.uz

Submission #1036644

# Submission time Handle Problem Language Result Execution time Memory
1036644 2024-07-27T15:06:22 Z hotboy2703 Bodyguard (JOI21_bodyguard) C++17
100 / 100
 2765 ms 708016 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1822 ms 414360 KB Output is correct
2 Correct 1624 ms 416228 KB Output is correct
3 Correct 1237 ms 325696 KB Output is correct
4 Correct 1002 ms 203272 KB Output is correct
5 Correct 1894 ms 680536 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 415572 KB Output is correct
2 Correct 788 ms 415416 KB Output is correct
3 Correct 789 ms 409796 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 764 ms 415468 KB Output is correct
6 Correct 740 ms 415548 KB Output is correct
7 Correct 717 ms 414804 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 415572 KB Output is correct
2 Correct 788 ms 415416 KB Output is correct
3 Correct 789 ms 409796 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 764 ms 415468 KB Output is correct
6 Correct 740 ms 415548 KB Output is correct
7 Correct 717 ms 414804 KB Output is correct
8 Correct 730 ms 415816 KB Output is correct
9 Correct 747 ms 415532 KB Output is correct
10 Correct 725 ms 409392 KB Output is correct
11 Correct 5 ms 1364 KB Output is correct
12 Correct 736 ms 415852 KB Output is correct
13 Correct 691 ms 415572 KB Output is correct
14 Correct 731 ms 415808 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 415572 KB Output is correct
2 Correct 788 ms 415416 KB Output is correct
3 Correct 789 ms 409796 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 764 ms 415468 KB Output is correct
6 Correct 740 ms 415548 KB Output is correct
7 Correct 717 ms 414804 KB Output is correct
8 Correct 730 ms 415816 KB Output is correct
9 Correct 747 ms 415532 KB Output is correct
10 Correct 725 ms 409392 KB Output is correct
11 Correct 5 ms 1364 KB Output is correct
12 Correct 736 ms 415852 KB Output is correct
13 Correct 691 ms 415572 KB Output is correct
14 Correct 731 ms 415808 KB Output is correct
15 Correct 771 ms 418788 KB Output is correct
16 Correct 745 ms 418904 KB Output is correct
17 Correct 751 ms 413772 KB Output is correct
18 Correct 17 ms 4192 KB Output is correct
19 Correct 789 ms 419500 KB Output is correct
20 Correct 742 ms 418424 KB Output is correct
21 Correct 757 ms 420272 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1822 ms 414360 KB Output is correct
2 Correct 1624 ms 416228 KB Output is correct
3 Correct 1237 ms 325696 KB Output is correct
4 Correct 1002 ms 203272 KB Output is correct
5 Correct 1894 ms 680536 KB Output is correct
6 Correct 796 ms 415572 KB Output is correct
7 Correct 788 ms 415416 KB Output is correct
8 Correct 789 ms 409796 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 764 ms 415468 KB Output is correct
11 Correct 740 ms 415548 KB Output is correct
12 Correct 717 ms 414804 KB Output is correct
13 Correct 730 ms 415816 KB Output is correct
14 Correct 747 ms 415532 KB Output is correct
15 Correct 725 ms 409392 KB Output is correct
16 Correct 5 ms 1364 KB Output is correct
17 Correct 736 ms 415852 KB Output is correct
18 Correct 691 ms 415572 KB Output is correct
19 Correct 731 ms 415808 KB Output is correct
20 Correct 771 ms 418788 KB Output is correct
21 Correct 745 ms 418904 KB Output is correct
22 Correct 751 ms 413772 KB Output is correct
23 Correct 17 ms 4192 KB Output is correct
24 Correct 789 ms 419500 KB Output is correct
25 Correct 742 ms 418424 KB Output is correct
26 Correct 757 ms 420272 KB Output is correct
27 Correct 2765 ms 674208 KB Output is correct
28 Correct 2282 ms 674184 KB Output is correct
29 Correct 2289 ms 708016 KB Output is correct
30 Correct 1212 ms 244364 KB Output is correct
31 Correct 1373 ms 586708 KB Output is correct
32 Correct 2440 ms 644188 KB Output is correct
33 Correct 1809 ms 692460 KB Output is correct