oj.uz

Submission #577492

# Submission time Handle Problem Language Result Execution time Memory
577492 2022-06-14T21:42:10 Z inksamurai Bodyguard (JOI21_bodyguard) C++17
42 / 100
 10581 ms 1663444 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){
		assert(pns[i]%2==0);
		cout<<pns[i]/2<<"\n";
	}
//
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6414 ms 886668 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 10054 ms 1659156 KB Output is correct
2 Correct 10542 ms 1659124 KB Output is correct
3 Correct 9906 ms 1658168 KB Output is correct
4 Correct 1118 ms 185100 KB Output is correct
5 Correct 7003 ms 1152504 KB Output is correct
6 Correct 8131 ms 1394360 KB Output is correct
7 Correct 9786 ms 1656788 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10054 ms 1659156 KB Output is correct
2 Correct 10542 ms 1659124 KB Output is correct
3 Correct 9906 ms 1658168 KB Output is correct
4 Correct 1118 ms 185100 KB Output is correct
5 Correct 7003 ms 1152504 KB Output is correct
6 Correct 8131 ms 1394360 KB Output is correct
7 Correct 9786 ms 1656788 KB Output is correct
8 Correct 10581 ms 1659388 KB Output is correct
9 Correct 9762 ms 1659300 KB Output is correct
10 Correct 9802 ms 1658380 KB Output is correct
11 Correct 976 ms 185316 KB Output is correct
12 Correct 7029 ms 1152748 KB Output is correct
13 Correct 7715 ms 1394728 KB Output is correct
14 Correct 6641 ms 1152636 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10054 ms 1659156 KB Output is correct
2 Correct 10542 ms 1659124 KB Output is correct
3 Correct 9906 ms 1658168 KB Output is correct
4 Correct 1118 ms 185100 KB Output is correct
5 Correct 7003 ms 1152504 KB Output is correct
6 Correct 8131 ms 1394360 KB Output is correct
7 Correct 9786 ms 1656788 KB Output is correct
8 Correct 10581 ms 1659388 KB Output is correct
9 Correct 9762 ms 1659300 KB Output is correct
10 Correct 9802 ms 1658380 KB Output is correct
11 Correct 976 ms 185316 KB Output is correct
12 Correct 7029 ms 1152748 KB Output is correct
13 Correct 7715 ms 1394728 KB Output is correct
14 Correct 6641 ms 1152636 KB Output is correct
15 Correct 10349 ms 1663444 KB Output is correct
16 Correct 10494 ms 1662952 KB Output is correct
17 Correct 10019 ms 1661072 KB Output is correct
18 Correct 983 ms 188092 KB Output is correct
19 Correct 6920 ms 1155740 KB Output is correct
20 Correct 7725 ms 1397888 KB Output is correct
21 Correct 6604 ms 1153448 KB Output is correct

Subtask #5
0 / 52.0

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