Submission #622843

#	Time	Username	Problem	Language	Result	Execution time	Memory
622843		errorgorn	Bodyguard (JOI21_bodyguard)	C++17	100 / 100	5947 ms	649520 KiB

bodyguard

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define i4 tuple<int,int,int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct line{
	int m,c;
	
	int eval(int x){
		return m*x+c;
	}
};

struct node{
	int s,e,m;
	line val={0,-(int)1e18};
	node *l=nullptr,*r=nullptr;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
	}
	
	void update(line i){
		bool lo=val.eval(s)<i.eval(s);
		bool mi=val.eval(m)<i.eval(m);
		bool hi=val.eval(e)<i.eval(e);
		
		if (mi) swap(i,val);
		
		if (i.c==-1e18 || lo==hi) return;
		
		if (lo!=mi && s!=m){
			if (l==nullptr) l=new node(s,m-1);
			l->update(i);
		}
		if (mi!=hi && m!=e){
			if (r==nullptr) r=new node(m+1,e);
			r->update(i);
		}
	}
	
	int query(int x){
		if (x<m){
			if (l==nullptr) return val.eval(x);
			else return max(val.eval(x),l->query(x));
		}
		else if (m<x){
			if (r==nullptr) return val.eval(x);
			else return max(val.eval(x),r->query(x));
		}
		else return val.eval(x);
	}
} *root; //[0,2e9]

int n,q;
ii arr[2805],brr[2805];
int cost[2805];

vector<int> vx,vy;
map<int,vector<iii> > mx,my;

int up[5605][5605];
int ri[5605][5605];
int grid[5605][5605];

vector<i4> q1,q2;
int ans[3000005];

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>q;
	
	int a,b,c;
	rep(x,0,n){
		cin>>a>>b>>c>>cost[x];
		arr[x]={a+b,a-b};
		brr[x]=arr[x];
		
		if (b<c) brr[x].fi+=2*(c-b);
		else brr[x].se+=2*(b-c);
		cost[x]/=2;
	}
	
	//rep(x,0,n){
		//cout<<arr[x].fi<<" "<<arr[x].se<<endl;
		//cout<<brr[x].fi<<" "<<brr[x].se<<endl;
		//cout<<cost[x]<<endl;
		//cout<<endl;
	//}
	
	rep(x,0,n){
		vx.pub(arr[x].fi),vx.pub(brr[x].fi);
		vy.pub(arr[x].se),vy.pub(brr[x].se);
		
		if (arr[x].fi==brr[x].fi) mx[arr[x].fi].pub({arr[x].se,brr[x].se,cost[x]});
		else my[arr[x].se].pub({arr[x].fi,brr[x].fi,cost[x]});
	}
	
	sort(all(vx)); vx.erase(unique(all(vx)),vx.end());
	sort(all(vy)); vy.erase(unique(all(vy)),vy.end());
	
	//for (auto it:vx) cout<<it<<" "; cout<<endl;
	//for (auto it:vy) cout<<it<<" "; cout<<endl;
	
	rep(x,0,sz(vx)){
		vector<iii> v=mx[vx[x]];
		
		vector<ii> ins,del;
		for (auto [a,b,c]:v){
			ins.pub({a,c});
			del.pub({b,c});
		}
		
		sort(all(ins)); reverse(all(ins));
		sort(all(del)); reverse(all(del));
		
		multiset<int,greater<int> > s;
		rep(y,0,sz(vy)){
			while (!ins.empty() && ins.back().fi==vy[y]){
				s.insert(ins.back().se);
				ins.pob();
			}
			while (!del.empty() && del.back().fi==vy[y]){
				s.erase(s.find(del.back().se));
				del.pob();
			}
			
			if (!s.empty()) up[x][y+1]=*s.begin();
		}
	}
	
	rep(y,0,sz(vy)){
		vector<iii> v=my[vy[y]];
		
		vector<ii> ins,del;
		for (auto [a,b,c]:v){
			ins.pub({a,c});
			del.pub({b,c});
		}
		
		sort(all(ins)); reverse(all(ins));
		sort(all(del)); reverse(all(del));
		
		multiset<int,greater<int> > s;
		rep(x,0,sz(vx)){
			while (!ins.empty() && ins.back().fi==vx[x]){
				s.insert(ins.back().se);
				ins.pob();
			}
			while (!del.empty() && del.back().fi==vx[x]){
				s.erase(s.find(del.back().se));
				del.pob();
			}
			
			if (!s.empty()) ri[x+1][y]=*s.begin();
		}
	}
	
	//rep(x,0,sz(vx)){
		//rep(y,0,sz(vy)) cout<<up[x][y]<<" "; cout<<endl;
	//} cout<<endl;
	//rep(x,0,sz(vx)){
		//rep(y,0,sz(vy)) cout<<ri[x][y]<<" "; cout<<endl;
	//} cout<<endl;
	
	rep(x,sz(vx),0) rep(y,sz(vy),0){
		if (x!=sz(vx)-1){
			grid[x][y]=max(grid[x][y],grid[x+1][y]+ri[x+1][y]*(vx[x+1]-vx[x]));
		}
		if (y!=sz(vy)-1){
			grid[x][y]=max(grid[x][y],grid[x][y+1]+up[x][y+1]*(vy[y+1]-vy[y]));
		}
	}
	
	//rep(x,0,sz(vx)){
		//rep(y,0,sz(vy)) cout<<grid[x][y]<<" "; cout<<endl;
	//} cout<<endl;
	
	rep(x,0,q){
		cin>>a>>b;
		tie(a,b)=ii(a+b,a-b);
		
		//cout<<a<<" "<<b<<endl;	
		
		a=max(a,vx[0]),b=max(b,vy[0]);
		if (a>vx.back() || b>vy.back()) continue;
		
		int a2=lb(all(vx),a)-vx.begin(),b2=lb(all(vy),b)-vy.begin();
		
		q1.pub({b2,a2,b,x});
		q2.pub({a2,b2,a,x});
		
		//int ans=0;
		//rep(x,a2,sz(vx)){
			//int temp=grid[x][b2]+up[x][b2]*(vy[b2]-b);
			//ans=max(ans,temp);
		//}
		//rep(y,b2,sz(vy)){
			//int temp=grid[a2][y]+ri[a2][y]*(vx[a2]-a);
			//ans=max(ans,temp);
		//}
		//cout<<ans<<endl;
	}
	
	sort(all(q1)); sort(all(q2));
	
	rep(y,sz(vy),0){ //process q1
		root=new node(-1000000000,2000000000);
		rep(x,sz(vx),0){
			root->update({-up[x][y],grid[x][y]+up[x][y]*vy[y]});
			
			while (!q1.empty() && get<0>(q1.back())==y && get<1>(q1.back())==x){
				int b=get<2>(q1.back()),idx=get<3>(q1.back()); q1.pob();
				ans[idx]=max(ans[idx],root->query(b));
			}
		}
	}
	
	rep(x,sz(vx),0){ //process q1
		root=new node(-1000000000,2000000000);
		rep(y,sz(vy),0){
			root->update({-ri[x][y],grid[x][y]+ri[x][y]*vx[x]});
			
			while (!q2.empty() && get<0>(q2.back())==x && get<1>(q2.back())==y){
				int a=get<2>(q2.back()),idx=get<3>(q2.back()); q2.pob();
				ans[idx]=max(ans[idx],root->query(a));
			}
		}
	}
	
	rep(x,0,q) cout<<ans[x]<<endl;
}

Compilation message (stderr)

bodyguard.cpp: In constructor 'node::node(long long int, long long int)':
bodyguard.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 52 / 52