Submission #1181733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181733		PieArmy	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	846 ms	70908 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

const int inf=2e9+5;

struct Seg{
	int n;
	bool b;
	vector<pair<int,int>>tree,arr;
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=arr[left];
			return;
		}
		const int mid=(left+right)>>1;
		build(node*2,left,mid);
		build(node*2+1,mid+1,right);
		tree[node]=tree[node*2];
		if((tree[node]<tree[node*2+1])==b)tree[node]=tree[node*2+1];
	}
	Seg(vector<pair<int,int>>Arr,bool buyuk){
		arr=Arr;
		n=arr.size();
		tree.resize(n<<2);
		b=buyuk;
		build();
	}
	void sil(int tar,int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]={inf*(b?-1:1),inf*(b?-1:1)};
			return;
		}
		const int mid=(left+right)>>1;
		if(tar>mid)sil(tar,node*2+1,mid+1,right);
		else sil(tar,node*2,left,mid);
		tree[node]=tree[node*2];
		if((tree[node]<tree[node*2+1])==b)tree[node]=tree[node*2+1];
	}
	int l,r;
	pair<int,int> qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r)return tree[node];
		if(left>r||right<l)return pair<int,int>{inf*(b?-1:1),inf*(b?-1:1)};
		const int mid=(left+right)>>1;
		pair<int,int>res=qu(node*2,left,mid),res2=qu(node*2+1,mid+1,right);
		if((res<res2)==b)return res2;
		return res;
	}
	pair<int,int> query(int lef,int rig){
		l=lef;r=rig;
		if(lef>rig)return pair<int,int>{inf*(b?-1:1),inf*(b?-1:1)};
		return qu();
	}
};

int n;
vector<pair<int,int>>arr,p;
set<pair<int,int>>st;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n;
	arr.resize(n);
	for(int i=0;i<n;i++){
		cin>>arr[i].fr>>arr[i].sc;
	}
	sort(arr.begin(),arr.end());
	for(int i=0;i<n;i++){
		p.pb({arr[i].fr+arr[i].sc,i});
	}
	Seg mn(p,0);
	for(int i=0;i<n;i++){
		p[i]={arr[i].fr-arr[i].sc,i};
	}
	Seg mx(p,1);
	for(int i=0;i<n;i++){
		st.insert({-arr[i].sc,i});
	}
	int ans=0;
	while(st.size()){
		ans++;
		int pos=st.begin()->sc;
		st.erase(st.begin());
		while(true){
			pair<int,int>p=mn.query(pos+1,n-1);
			if(p.fr>arr[pos].fr+arr[pos].sc)break;
			st.erase({-arr[p.sc].sc,p.sc});
			mn.sil(p.sc);
		}
		while(true){
			pair<int,int>p=mx.query(0,pos-1);
			if(p.fr<arr[pos].fr-arr[pos].sc)break;
			st.erase({-arr[p.sc].sc,p.sc});
			mx.sil(p.sc);
		}
	}
	cout<<ans;
}

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