oj.uz

답안 #577495

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577495 2022-06-14T21:48:08 Z inksamurai Bodyguard (JOI21_bodyguard) C++17
100 / 100
 13004 ms 1975148 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>;


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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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