Submission #892271

#	Time	Username	Problem	Language	Result	Execution time	Memory
892271		LCJLY	Advertisement 2 (JOI23_ho_t2)	C++14	0 / 100	1168 ms	1048576 KiB

Main

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

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
//typedef pair<pii,pii>pi2;
typedef array<int,4>pi2;

inline pi2 combine(pi2 a, pi2 b){
	pi2 temp;
	//max pos min pos
	if(a[0]>=b[0]){
		temp[0]=a[0];
		temp[1]=a[1];
	}
	else{
		temp[0]=b[0];
		temp[1]=b[1];
	}
	
	if(a[2]<=b[2]){
		temp[2]=a[2];
		temp[3]=a[3];
	}
	else{
		temp[2]=b[2];
		temp[3]=b[3];
	}
	return temp;
}

pi2 undo={(int)-1e15,(int)-1,(int)1e15,(int)-1};

struct node{
	int s,e,m;
	node *l,*r;
	pi2 v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL){
		v=undo;
	}
	
	inline void inst(){
		if(l==NULL)l=new node(s,m);
		if(r==NULL)r=new node(m+1,e);
	}
	
	void upd(int x, pi2 y){
		if(s==e){
			v=y;
			return;
		}
		inst();
		if(x<=m)l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	pi2 query(int x, int y){
		if(x<=s&&y>=e) return v;
		inst();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){	
	int n;
	cin >> n;
	pii arr[n];
	int maxn=1000000005;
	node left(0,maxn);
	node right(0,maxn);
	bool done[n];
	memset(done,0,sizeof(done));
	map<int,pii>mp;
	int cnt=n;
	for(int x=0;x<n;x++){
		cin >> arr[x].first >> arr[x].second;
		if(mp.find(arr[x].first)==mp.end()){
			mp[arr[x].first]={arr[x].second,x};
		}
		else{
			if(mp[arr[x].first].first<=arr[x].second){
				pii hold=mp[arr[x].first];
				done[hold.second]=true;
				cnt--;
				mp[arr[x].first]={arr[x].second,x};
			}
		}
	}
	
	priority_queue<pii>pq;
	for(auto it:mp){
		int l=it.first-it.second.first;
		int r=it.first+it.second.first;
		
		pq.push({it.second.first,it.second.second});
		left.upd(it.first,{l,it.second.second,l,it.second.second});
		right.upd(it.first,{r,it.second.second,r,it.second.second});
	}
	
	int counter=0;
	
	while(cnt>0){
		pii hold={0,0};
		while(!pq.empty()){
			hold=pq.top();
			pq.pop();
			if(!done[hold.second]) break;
		}
		
		done[hold.second]=true;
		left.upd(arr[hold.second].first,undo);
		right.upd(arr[hold.second].first,undo);
		int val=arr[hold.second].first-arr[hold.second].second;
		cnt--;
		while(cnt){
			//left
			pi2 hold2=left.query(0,arr[hold.second].first-1);
			if(hold2[1]==-1) break;
			int index=hold2[1];
			if(val>hold2[0]) break;
			done[index]=true;
			left.upd(arr[index].first,undo);
			right.upd(arr[index].first,undo);
			cnt--;
		}
		
		val=arr[hold.second].first+arr[hold.second].second;
		while(cnt){
			//right
			pi2 hold2=right.query(arr[hold.second].first+1,maxn);
			if(hold2[3]==-1) break;
			int index=hold2[3];
			if(val<hold2[2]) break;
			done[index]=true;
			left.upd(arr[index].first,undo);
			right.upd(arr[index].first,undo);
			cnt--;
		}
		counter++;
	}
	
	cout << counter;
	
}

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("in.txt", "r", stdin);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}



		


		
		
	

• Subtask 1: 0 / 10
• Subtask 2: 0 / 23
• Subtask 3: 0 / 36
• Subtask 4: 0 / 31