oj.uz

Submission #622843

# Submission time Handle Problem Language Result Execution time Memory
622843 2022-08-04T16:31:35 Z errorgorn Bodyguard (JOI21_bodyguard) C++17
100 / 100
 5947 ms 649520 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4982 ms 460120 KB Output is correct
2 Correct 5040 ms 463048 KB Output is correct
3 Correct 2889 ms 287388 KB Output is correct
4 Correct 1627 ms 175388 KB Output is correct
5 Correct 4274 ms 554308 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1664 ms 321308 KB Output is correct
2 Correct 1931 ms 320144 KB Output is correct
3 Correct 1658 ms 329220 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 2128 ms 369420 KB Output is correct
6 Correct 1670 ms 277152 KB Output is correct
7 Correct 1312 ms 241624 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1664 ms 321308 KB Output is correct
2 Correct 1931 ms 320144 KB Output is correct
3 Correct 1658 ms 329220 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 2128 ms 369420 KB Output is correct
6 Correct 1670 ms 277152 KB Output is correct
7 Correct 1312 ms 241624 KB Output is correct
8 Correct 1579 ms 320416 KB Output is correct
9 Correct 1676 ms 320788 KB Output is correct
10 Correct 2122 ms 328116 KB Output is correct
11 Correct 6 ms 1748 KB Output is correct
12 Correct 2182 ms 369740 KB Output is correct
13 Correct 1626 ms 277540 KB Output is correct
14 Correct 2730 ms 275388 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1664 ms 321308 KB Output is correct
2 Correct 1931 ms 320144 KB Output is correct
3 Correct 1658 ms 329220 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 2128 ms 369420 KB Output is correct
6 Correct 1670 ms 277152 KB Output is correct
7 Correct 1312 ms 241624 KB Output is correct
8 Correct 1579 ms 320416 KB Output is correct
9 Correct 1676 ms 320788 KB Output is correct
10 Correct 2122 ms 328116 KB Output is correct
11 Correct 6 ms 1748 KB Output is correct
12 Correct 2182 ms 369740 KB Output is correct
13 Correct 1626 ms 277540 KB Output is correct
14 Correct 2730 ms 275388 KB Output is correct
15 Correct 1675 ms 324628 KB Output is correct
16 Correct 1750 ms 324624 KB Output is correct
17 Correct 1622 ms 332728 KB Output is correct
18 Correct 28 ms 3388 KB Output is correct
19 Correct 2177 ms 373344 KB Output is correct
20 Correct 2003 ms 281060 KB Output is correct
21 Correct 5947 ms 278460 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4982 ms 460120 KB Output is correct
2 Correct 5040 ms 463048 KB Output is correct
3 Correct 2889 ms 287388 KB Output is correct
4 Correct 1627 ms 175388 KB Output is correct
5 Correct 4274 ms 554308 KB Output is correct
6 Correct 1664 ms 321308 KB Output is correct
7 Correct 1931 ms 320144 KB Output is correct
8 Correct 1658 ms 329220 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct
10 Correct 2128 ms 369420 KB Output is correct
11 Correct 1670 ms 277152 KB Output is correct
12 Correct 1312 ms 241624 KB Output is correct
13 Correct 1579 ms 320416 KB Output is correct
14 Correct 1676 ms 320788 KB Output is correct
15 Correct 2122 ms 328116 KB Output is correct
16 Correct 6 ms 1748 KB Output is correct
17 Correct 2182 ms 369740 KB Output is correct
18 Correct 1626 ms 277540 KB Output is correct
19 Correct 2730 ms 275388 KB Output is correct
20 Correct 1675 ms 324628 KB Output is correct
21 Correct 1750 ms 324624 KB Output is correct
22 Correct 1622 ms 332728 KB Output is correct
23 Correct 28 ms 3388 KB Output is correct
24 Correct 2177 ms 373344 KB Output is correct
25 Correct 2003 ms 281060 KB Output is correct
26 Correct 5947 ms 278460 KB Output is correct
27 Correct 4318 ms 649140 KB Output is correct
28 Correct 4206 ms 649520 KB Output is correct
29 Correct 3380 ms 597180 KB Output is correct
30 Correct 1051 ms 141408 KB Output is correct
31 Correct 3316 ms 558868 KB Output is correct
32 Correct 4556 ms 576200 KB Output is correct
33 Correct 3605 ms 566436 KB Output is correct