oj.uz

Submission #577488

# Submission time Handle Problem Language Result Execution time Memory
577488 2022-06-14T21:33:16 Z inksamurai Bodyguard (JOI21_bodyguard) C++17
42 / 100
 10865 ms 1663836 KB 
#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>;

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={(int)1e15};
	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]=cosu;
				}
			}else{
				rng(j,s.fi,t.fi){
					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){
		cout<<pns[i]/2<<"\n";
	}
//
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6113 ms 889660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10350 ms 1659324 KB Output is correct
2 Correct 10269 ms 1659264 KB Output is correct
3 Correct 9853 ms 1658288 KB Output is correct
4 Correct 1033 ms 185296 KB Output is correct
5 Correct 6783 ms 1152692 KB Output is correct
6 Correct 7834 ms 1394456 KB Output is correct
7 Correct 9536 ms 1656868 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10350 ms 1659324 KB Output is correct
2 Correct 10269 ms 1659264 KB Output is correct
3 Correct 9853 ms 1658288 KB Output is correct
4 Correct 1033 ms 185296 KB Output is correct
5 Correct 6783 ms 1152692 KB Output is correct
6 Correct 7834 ms 1394456 KB Output is correct
7 Correct 9536 ms 1656868 KB Output is correct
8 Correct 10190 ms 1659432 KB Output is correct
9 Correct 10170 ms 1659428 KB Output is correct
10 Correct 9852 ms 1658464 KB Output is correct
11 Correct 1004 ms 185444 KB Output is correct
12 Correct 6835 ms 1152988 KB Output is correct
13 Correct 7879 ms 1394700 KB Output is correct
14 Correct 7033 ms 1152860 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10350 ms 1659324 KB Output is correct
2 Correct 10269 ms 1659264 KB Output is correct
3 Correct 9853 ms 1658288 KB Output is correct
4 Correct 1033 ms 185296 KB Output is correct
5 Correct 6783 ms 1152692 KB Output is correct
6 Correct 7834 ms 1394456 KB Output is correct
7 Correct 9536 ms 1656868 KB Output is correct
8 Correct 10190 ms 1659432 KB Output is correct
9 Correct 10170 ms 1659428 KB Output is correct
10 Correct 9852 ms 1658464 KB Output is correct
11 Correct 1004 ms 185444 KB Output is correct
12 Correct 6835 ms 1152988 KB Output is correct
13 Correct 7879 ms 1394700 KB Output is correct
14 Correct 7033 ms 1152860 KB Output is correct
15 Correct 10270 ms 1663304 KB Output is correct
16 Correct 10865 ms 1663836 KB Output is correct
17 Correct 9965 ms 1662056 KB Output is correct
18 Correct 998 ms 188584 KB Output is correct
19 Correct 6777 ms 1156416 KB Output is correct
20 Correct 7802 ms 1398524 KB Output is correct
21 Correct 6750 ms 1153976 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 6113 ms 889660 KB Output isn't correct
2 Halted 0 ms 0 KB -