Submission #577495

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
577495	2022-06-14T21:48:08 Z	inksamurai	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	13004 ms	1975148 KB

bodyguard

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3MJnHrA ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

// kactl line container
// cht on max point
// use monotocity if possible
// o(nlgn)

// APIO'10 P1
// DMOJ Yet Another Contest 2 P6 - Travel Budget


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

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll 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(ll k, ll 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));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};

using T=pair<int,pair<pii,pii>>;

using Q=pair<int,pii>;


const int inf=1e15;

signed main(){
_3MJnHrA;
	int n,q;
	cin>>n>>q;

	vec(T) a(n);
	rep(i,n){
		int _t,_l,_r,_c;
		cin>>_t>>_l>>_r>>_c;
		pii s={_t,_l};
		pii t={_t+abs(_r-_l),_r};
		s={s.fi-s.se,s.fi+s.se};
		t={t.fi-t.se,t.fi+t.se};
		a[i]=T(_c,{s,t});
	}

	vi xys={inf};
	rep(i,n){
		pii s=a[i].se.fi,t=a[i].se.se;
		// print(s.fi,s.se,t.fi,t.se);
		xys.pb(s.fi);
		xys.pb(s.se);
		xys.pb(t.fi);
		xys.pb(t.se);
	}
	sort(xys.begin(), xys.end());
	xys.erase(unique(xys.begin(), xys.end()),xys.end());

	auto ced=[&](int x){
		return (int)(lower_bound(xys.begin(), xys.end(),x)-xys.begin());
	};

	int _n=sz(xys);
	vec(vi) movex(_n,vi(_n)),movey;
	movey=movex;
	{
		rep(i,n){
			int cosu=a[i].fi;
			pii s=a[i].se.fi,t=a[i].se.se;
			int type=s.fi==t.fi;
			s.fi=ced(s.fi);
			s.se=ced(s.se);
			t.fi=ced(t.fi);
			t.se=ced(t.se);
			// print(s.fi,s.se,t.fi,t.se);
			if(type){
				rng(j,s.se,t.se){
					movey[s.fi][j]=max(movey[s.fi][j],cosu);
				}
			}else{
				rng(j,s.fi,t.fi){
					movex[j][s.se]=max(movex[j][s.se],cosu);
				}
			}
		}
	}

	vec(vi) dp(_n,vi(_n));
	per(i,_n){
		per(j,_n){
			if(i+1<_n){
				dp[i][j]=max(dp[i][j],dp[i+1][j]+(xys[i+1]-xys[i])*movex[i][j]);
			}
			if(j+1<_n){
				dp[i][j]=max(dp[i][j],dp[i][j+1]+(xys[j+1]-xys[j])*movey[i][j]);
			}
		}
	}

	vi pns(q);
	vec(vec(Q)) adqry_y(_n),adqry_x;
	adqry_x=adqry_y;
	rep(i,q){
		int t,_x;
		cin>>t>>_x;
		pii p={t-_x,t+_x};
		int x=p.fi,y=p.se;
		p.fi=ced(p.fi);
		p.se=ced(p.se);
		pns[i]=max(pns[i],dp[p.fi][p.se]);
		if(p.se){
			adqry_y[p.se].pb({p.fi,{y,i}});
		}
		if(p.fi){
			adqry_x[p.fi].pb({p.se,{x,i}});
		}
		// if(p.se){
		// 	rng(i,p.fi,_n){
		// 		ans=max(ans,dp[i][p.se]+movey[i][p.se-1]*(xys[p.se]-y));
		// 	}
		// }
		// if(p.fi){
		// 	rng(j,p.se,_n){
		// 		ans=max(ans,dp[p.fi][j]+movex[p.fi-1][j]*(xys[p.fi]-x));
		// 	}
		// }
	}

	rng(i,1,_n){
		sort(adqry_x[i].begin(),adqry_x[i].end());
		LineContainer cht;
		cht.add(0,0);
		per(j,_n){
			cht.add(-movex[i-1][j],movex[i-1][j]*xys[i]+dp[i][j]);
			while(sz(adqry_x[i])){
				Q p=adqry_x[i].back();
				if(p.fi>=j){
					// print(p.se.fi,"ho");
					pns[p.se.se]=max(pns[p.se.se],cht.query(p.se.fi));
					adqry_x[i].pop_back();
				}else{
					break;
				}
			}
		}
	}
	rng(j,1,_n){
		sort(adqry_y[j].begin(),adqry_y[j].end());
		LineContainer cht;
		cht.add(0,0);
		per(i,_n){
			cht.add(-movey[i][j-1],movey[i][j-1]*xys[j]+dp[i][j]);
			while(sz(adqry_y[j])){
				Q p=adqry_y[j].back();
				if(p.fi>=i){
					// print(p.se.fi,"ho",cht.query(p.se.fi));
					pns[p.se.se]=max(pns[p.se.se],cht.query(p.se.fi));
					adqry_y[j].pop_back();
				}else{
					break;
				}
			}
		}
	}

	rep(i,q){
		assert(pns[i]%2==0);
		cout<<pns[i]/2<<"\n";
	}
//
	return 0;
}

Subtask #1

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6389 ms	886580 KB	Output is correct
2	Correct	6636 ms	892444 KB	Output is correct
3	Correct	2905 ms	374340 KB	Output is correct
4	Correct	3056 ms	406988 KB	Output is correct
5	Correct	8233 ms	1311340 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10773 ms	1659160 KB	Output is correct
2	Correct	10907 ms	1659296 KB	Output is correct
3	Correct	10260 ms	1658260 KB	Output is correct
4	Correct	1002 ms	185108 KB	Output is correct
5	Correct	7226 ms	1152712 KB	Output is correct
6	Correct	8342 ms	1394364 KB	Output is correct
7	Correct	10230 ms	1656792 KB	Output is correct

Subtask #3

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10773 ms	1659160 KB	Output is correct
2	Correct	10907 ms	1659296 KB	Output is correct
3	Correct	10260 ms	1658260 KB	Output is correct
4	Correct	1002 ms	185108 KB	Output is correct
5	Correct	7226 ms	1152712 KB	Output is correct
6	Correct	8342 ms	1394364 KB	Output is correct
7	Correct	10230 ms	1656792 KB	Output is correct
8	Correct	10929 ms	1659304 KB	Output is correct
9	Correct	10955 ms	1659308 KB	Output is correct
10	Correct	10516 ms	1658280 KB	Output is correct
11	Correct	1004 ms	185360 KB	Output is correct
12	Correct	7105 ms	1152748 KB	Output is correct
13	Correct	8018 ms	1394588 KB	Output is correct
14	Correct	6794 ms	1152744 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10773 ms	1659160 KB	Output is correct
2	Correct	10907 ms	1659296 KB	Output is correct
3	Correct	10260 ms	1658260 KB	Output is correct
4	Correct	1002 ms	185108 KB	Output is correct
5	Correct	7226 ms	1152712 KB	Output is correct
6	Correct	8342 ms	1394364 KB	Output is correct
7	Correct	10230 ms	1656792 KB	Output is correct
8	Correct	10929 ms	1659304 KB	Output is correct
9	Correct	10955 ms	1659308 KB	Output is correct
10	Correct	10516 ms	1658280 KB	Output is correct
11	Correct	1004 ms	185360 KB	Output is correct
12	Correct	7105 ms	1152748 KB	Output is correct
13	Correct	8018 ms	1394588 KB	Output is correct
14	Correct	6794 ms	1152744 KB	Output is correct
15	Correct	10358 ms	1662928 KB	Output is correct
16	Correct	10398 ms	1662952 KB	Output is correct
17	Correct	10399 ms	1661060 KB	Output is correct
18	Correct	992 ms	187972 KB	Output is correct
19	Correct	6831 ms	1155748 KB	Output is correct
20	Correct	8343 ms	1397904 KB	Output is correct
21	Correct	6809 ms	1153404 KB	Output is correct

Subtask #5

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6389 ms	886580 KB	Output is correct
2	Correct	6636 ms	892444 KB	Output is correct
3	Correct	2905 ms	374340 KB	Output is correct
4	Correct	3056 ms	406988 KB	Output is correct
5	Correct	8233 ms	1311340 KB	Output is correct
6	Correct	10773 ms	1659160 KB	Output is correct
7	Correct	10907 ms	1659296 KB	Output is correct
8	Correct	10260 ms	1658260 KB	Output is correct
9	Correct	1002 ms	185108 KB	Output is correct
10	Correct	7226 ms	1152712 KB	Output is correct
11	Correct	8342 ms	1394364 KB	Output is correct
12	Correct	10230 ms	1656792 KB	Output is correct
13	Correct	10929 ms	1659304 KB	Output is correct
14	Correct	10955 ms	1659308 KB	Output is correct
15	Correct	10516 ms	1658280 KB	Output is correct
16	Correct	1004 ms	185360 KB	Output is correct
17	Correct	7105 ms	1152748 KB	Output is correct
18	Correct	8018 ms	1394588 KB	Output is correct
19	Correct	6794 ms	1152744 KB	Output is correct
20	Correct	10358 ms	1662928 KB	Output is correct
21	Correct	10398 ms	1662952 KB	Output is correct
22	Correct	10399 ms	1661060 KB	Output is correct
23	Correct	992 ms	187972 KB	Output is correct
24	Correct	6831 ms	1155748 KB	Output is correct
25	Correct	8343 ms	1397904 KB	Output is correct
26	Correct	6809 ms	1153404 KB	Output is correct
27	Correct	13004 ms	1975148 KB	Output is correct
28	Correct	12809 ms	1971328 KB	Output is correct
29	Correct	12190 ms	1933492 KB	Output is correct
30	Correct	2677 ms	468680 KB	Output is correct
31	Correct	8085 ms	1329980 KB	Output is correct
32	Correct	9846 ms	1727072 KB	Output is correct
33	Correct	7488 ms	1255868 KB	Output is correct