oj.uz

Submission #887333

# Submission time Handle Problem Language Result Execution time Memory
887333 2023-12-14T09:17:47 Z willychan Bodyguard (JOI21_bodyguard) C++17
100 / 100
 9208 ms 674512 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
//#include<bits/extc++.h>
//__gnu_pbds

vector<ll> xd;
vector<ll> yd;
struct T{
	ll x1,y1;
	ll x2,y2;
} ;

struct lichao{
	struct line{
		ll m = 0 ;
		ll k = -1e18;
		ll operator()(ll x){
			return m*x+k;	
		}
	};
	struct node{
		line L;
		node* lc = nullptr;
		node* rc = nullptr;
		~node(){
			if(lc!=nullptr) delete(lc); 
			if(rc!=nullptr) delete(rc);
		}
	};
	node* head = new node();	
	void add(node* cur,ll L,ll R,line s){
		if(cur==nullptr) return;
		ll M = L+((R-L)/2);
		if(cur->L(M)<s(M)) swap(cur->L,s);
		if(L==R) return;
		if(s.m>cur->L.m){
			if(cur->rc==nullptr){
				cur->rc = new node();
				cur->rc->L = s;
				return;
			}
			add(cur->rc,M+1,R,s);
		}else{
			if(cur->lc==nullptr){
				cur->lc = new node();
				cur->lc->L = s;
				return;
			}
			add(cur->lc,L,M,s);
		}
	}

	ll query(node* cur,ll L,ll R,ll x){
		if(cur==nullptr) return -1e18;
		if(L==R) return cur->L(x);
		ll M = L+(R-L)/2;
		if(x>M) return max(cur->L(x),query(cur->rc,M+1,R,x));
		else return max(cur->L(x),query(cur->lc,L,M,x));
	}
	ll CX = 1e10;
	void insert(ll m,ll k){
		line p;		
		p.m = m;
		p.k = k;
		add(head,-CX,CX,p);
	}

	ll get(ll v){
		assert(abs(v)<CX);
		return query(head,-CX,CX,v);
	}
	
	~lichao(){
		delete(head);
	}
	
};



signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,Q;cin>>n>>Q;		
	vector<ll> C(n+1);
	vector<T> people(n+1);
	// input
	for(int i=1;i<=n;i++){
		int T,a,b;
		cin>>T>>a>>b>>C[i];
		C[i]/=2;
		people[i].x1 = a+T;
		people[i].y1 = T-a; 
		people[i].x2 = b+(abs(b-a)+T);
		people[i].y2 = (abs(b-a)+T)-b;
		xd.push_back(people[i].x1);
		yd.push_back(people[i].y1);
		xd.push_back(people[i].x2);
		yd.push_back(people[i].y2);
	}

	
	// cor com
	sort(xd.begin(),xd.end());
	xd.resize(unique(xd.begin(),xd.end())-xd.begin());
	sort(yd.begin(),yd.end());
	yd.resize(unique(yd.begin(),yd.end())-yd.begin());
	int X = xd.size();
	int Y = yd.size();
	vector<vector<ll> > dp(X+1,vector<ll>(Y+1,0));
	vector<vector<ll> >	costx(X+1,vector<ll>(Y+1,0));
	vector<vector<ll> >	costy(X+1,vector<ll>(Y+1,0));
	
	for(int i=1;i<=n;i++){
		people[i].x1 = lower_bound(xd.begin(),xd.end(),people[i].x1)-xd.begin();
		people[i].x2 = lower_bound(xd.begin(),xd.end(),people[i].x2)-xd.begin();
		people[i].y1 = lower_bound(yd.begin(),yd.end(),people[i].y1)-yd.begin();
		people[i].y2 = lower_bound(yd.begin(),yd.end(),people[i].y2)-yd.begin();
	}

	// cost init
	for(int i=1;i<=n;i++){
		if(people[i].x1==people[i].x2){
			for(int k = people[i].y1;k<people[i].y2;k++){
				costy[people[i].x1][k] = max(costy[people[i].x1][k],C[i]);
			}
		}else if(people[i].y1==people[i].y2){
			for(int k = people[i].x1;k<people[i].x2;k++){
				costx[k][people[i].y1] = max(costx[k][people[i].y1],C[i]);
			}
		}else{
			assert(1==0);
		}
	}
	// dp
	for(int x = X-1;x>=0;x--){
		for(int y=Y-1;y>=0;y--){
			if(y+1<Y) dp[x][y] = max(dp[x][y],dp[x][y+1]+(yd[y+1]-yd[y])*costy[x][y]);
			if(x+1<X) dp[x][y] = max(dp[x][y],dp[x+1][y]+(xd[x+1]-xd[x])*costx[x][y]);
		}
	}

	//ans
	vector<ll> ans(Q);
	vector<ll> qx(Q);
	vector<ll> qy(Q);
	vector<ll> qxB(Q);
	vector<ll> qyB(Q);
	vector<int> ord(Q);
	for(int i=0;i<Q;i++){
		ll t,x;cin>>t>>x;
		qx[i] = t+x;
		qy[i] = t-x;
		qxB[i] = upper_bound(xd.begin(),xd.end(),qx[i])-xd.begin();
		qyB[i] = upper_bound(yd.begin(),yd.end(),qy[i])-yd.begin();
		ord[i]=i;
	}

	sort(ord.begin(),ord.end(),[&](const int &a,const int &b){
		if(qyB[a]==qyB[b]) return qx[a]>qx[b];
		return qyB[a]<qyB[b];
	});
	int head = 0;	
	for(int y=0;y<Y;y++){
		lichao segy;
		for(int x=X-1;x>=0;x--){
			while(head<Q && qyB[ord[head]]==y && qx[ord[head]]>xd[x]){
				ans[ord[head]] = max(ans[ord[head]],segy.get(qy[ord[head]]));
				head++;
			}
			ll cy = (y==0)?(0):(costy[x][y-1]);
			segy.insert(-cy,dp[x][y]+cy*yd[y]);
		}
		while(head<Q && qyB[ord[head]]==y){
			ans[ord[head]] = max(ans[ord[head]],segy.get(qy[ord[head]]));
			head++; 
		}
	}
	sort(ord.begin(),ord.end(),[&](const int &a,const int &b){
		if(qxB[a]==qxB[b]) return qy[a]>qy[b];
		return qxB[a]<qxB[b];
	});
	head = 0;
	for(int x=0;x<X;x++){
		lichao segx;
		for(int y=Y-1;y>=0;y--){
			while(head<Q && qxB[ord[head]]==x && qy[ord[head]]>yd[y]){
				ans[ord[head]] = max(ans[ord[head]],segx.get(qx[ord[head]]));
				head++;
			}
			ll cx = (x==0)?(0):(costx[x-1][y]);
			segx.insert(-cx,dp[x][y]+cx*xd[x]);
		}
		while(head<Q && qxB[ord[head]]==x){
			ans[ord[head]] = max(ans[ord[head]],segx.get(qx[ord[head]]));
			head++;
		}
	}
	
	for(int i=0;i<Q;i++){
		cout<<ans[i]<<"\n";
	}

	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6407 ms 400912 KB Output is correct
2 Correct 6432 ms 416272 KB Output is correct
3 Correct 3219 ms 258644 KB Output is correct
4 Correct 2116 ms 192664 KB Output is correct
5 Correct 6354 ms 624136 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5165 ms 415824 KB Output is correct
2 Correct 4894 ms 416084 KB Output is correct
3 Correct 4758 ms 410048 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 3592 ms 415752 KB Output is correct
6 Correct 3557 ms 415604 KB Output is correct
7 Correct 3498 ms 415312 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5165 ms 415824 KB Output is correct
2 Correct 4894 ms 416084 KB Output is correct
3 Correct 4758 ms 410048 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 3592 ms 415752 KB Output is correct
6 Correct 3557 ms 415604 KB Output is correct
7 Correct 3498 ms 415312 KB Output is correct
8 Correct 4934 ms 416204 KB Output is correct
9 Correct 4838 ms 416356 KB Output is correct
10 Correct 4776 ms 409624 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 3638 ms 415916 KB Output is correct
13 Correct 3552 ms 415992 KB Output is correct
14 Correct 3803 ms 416048 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5165 ms 415824 KB Output is correct
2 Correct 4894 ms 416084 KB Output is correct
3 Correct 4758 ms 410048 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 3592 ms 415752 KB Output is correct
6 Correct 3557 ms 415604 KB Output is correct
7 Correct 3498 ms 415312 KB Output is correct
8 Correct 4934 ms 416204 KB Output is correct
9 Correct 4838 ms 416356 KB Output is correct
10 Correct 4776 ms 409624 KB Output is correct
11 Correct 4 ms 1116 KB Output is correct
12 Correct 3638 ms 415916 KB Output is correct
13 Correct 3552 ms 415992 KB Output is correct
14 Correct 3803 ms 416048 KB Output is correct
15 Correct 4990 ms 419212 KB Output is correct
16 Correct 4991 ms 419408 KB Output is correct
17 Correct 4877 ms 413848 KB Output is correct
18 Correct 21 ms 3972 KB Output is correct
19 Correct 3770 ms 418400 KB Output is correct
20 Correct 3657 ms 418580 KB Output is correct
21 Correct 3920 ms 418476 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6407 ms 400912 KB Output is correct
2 Correct 6432 ms 416272 KB Output is correct
3 Correct 3219 ms 258644 KB Output is correct
4 Correct 2116 ms 192664 KB Output is correct
5 Correct 6354 ms 624136 KB Output is correct
6 Correct 5165 ms 415824 KB Output is correct
7 Correct 4894 ms 416084 KB Output is correct
8 Correct 4758 ms 410048 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3592 ms 415752 KB Output is correct
11 Correct 3557 ms 415604 KB Output is correct
12 Correct 3498 ms 415312 KB Output is correct
13 Correct 4934 ms 416204 KB Output is correct
14 Correct 4838 ms 416356 KB Output is correct
15 Correct 4776 ms 409624 KB Output is correct
16 Correct 4 ms 1116 KB Output is correct
17 Correct 3638 ms 415916 KB Output is correct
18 Correct 3552 ms 415992 KB Output is correct
19 Correct 3803 ms 416048 KB Output is correct
20 Correct 4990 ms 419212 KB Output is correct
21 Correct 4991 ms 419408 KB Output is correct
22 Correct 4877 ms 413848 KB Output is correct
23 Correct 21 ms 3972 KB Output is correct
24 Correct 3770 ms 418400 KB Output is correct
25 Correct 3657 ms 418580 KB Output is correct
26 Correct 3920 ms 418476 KB Output is correct
27 Correct 9004 ms 674404 KB Output is correct
28 Correct 9208 ms 674512 KB Output is correct
29 Correct 7988 ms 653756 KB Output is correct
30 Correct 2493 ms 217248 KB Output is correct
31 Correct 5344 ms 558752 KB Output is correct
32 Correct 7014 ms 643764 KB Output is correct
33 Correct 5824 ms 636184 KB Output is correct