oj.uz

Submission #577486

# Submission time Handle Problem Language Result Execution time Memory
577486 2022-06-14T21:00:17 Z inksamurai Bodyguard (JOI21_bodyguard) C++17
42 / 100
 11173 ms 1662976 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)1e18};
	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 5980 ms 913836 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 10552 ms 1659336 KB Output is correct
2 Correct 10155 ms 1659268 KB Output is correct
3 Correct 9851 ms 1658276 KB Output is correct
4 Correct 979 ms 185288 KB Output is correct
5 Correct 6629 ms 1152688 KB Output is correct
6 Correct 7796 ms 1394452 KB Output is correct
7 Correct 9428 ms 1657012 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10552 ms 1659336 KB Output is correct
2 Correct 10155 ms 1659268 KB Output is correct
3 Correct 9851 ms 1658276 KB Output is correct
4 Correct 979 ms 185288 KB Output is correct
5 Correct 6629 ms 1152688 KB Output is correct
6 Correct 7796 ms 1394452 KB Output is correct
7 Correct 9428 ms 1657012 KB Output is correct
8 Correct 11173 ms 1659476 KB Output is correct
9 Correct 10379 ms 1659476 KB Output is correct
10 Correct 9732 ms 1658568 KB Output is correct
11 Correct 1004 ms 185448 KB Output is correct
12 Correct 6771 ms 1152956 KB Output is correct
13 Correct 7761 ms 1394700 KB Output is correct
14 Correct 6614 ms 1152744 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10552 ms 1659336 KB Output is correct
2 Correct 10155 ms 1659268 KB Output is correct
3 Correct 9851 ms 1658276 KB Output is correct
4 Correct 979 ms 185288 KB Output is correct
5 Correct 6629 ms 1152688 KB Output is correct
6 Correct 7796 ms 1394452 KB Output is correct
7 Correct 9428 ms 1657012 KB Output is correct
8 Correct 11173 ms 1659476 KB Output is correct
9 Correct 10379 ms 1659476 KB Output is correct
10 Correct 9732 ms 1658568 KB Output is correct
11 Correct 1004 ms 185448 KB Output is correct
12 Correct 6771 ms 1152956 KB Output is correct
13 Correct 7761 ms 1394700 KB Output is correct
14 Correct 6614 ms 1152744 KB Output is correct
15 Correct 10727 ms 1662924 KB Output is correct
16 Correct 10209 ms 1662976 KB Output is correct
17 Correct 9976 ms 1661064 KB Output is correct
18 Correct 1008 ms 187908 KB Output is correct
19 Correct 6656 ms 1155740 KB Output is correct
20 Correct 7800 ms 1397900 KB Output is correct
21 Correct 6633 ms 1153444 KB Output is correct

Subtask #5
0 / 52.0

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