Submission #741810

#	Time	Username	Problem	Language	Result	Execution time	Memory
741810		jamezzz	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	1135 ms	132576 KiB

Main

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define INF 2023456789
typedef pair<int,int> ii;

#define maxn 500005

int n,x[maxn],e[maxn],d[maxn];
vector<int> v;
set<ii> s1;

struct node{
	int s,e,m,v;
	node *l,*r;
	node(int _s,int _e){
		s=_s,e=_e,m=(s+e)>>1,v=-INF;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void up(int x,int nv){
		if(s==x&&e==x){v=nv;return;}
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		v=max(l->v,r->v);
	}
	int qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		else if(x>m)return r->qry(x,y);
		else return max(l->qry(x,m),r->qry(m+1,y));
	}
}*rt,*rt2;

int main(){
	sf("%d",&n);
	for(int i=0;i<n;++i){
		sf("%d%d",&x[i],&e[i]);
		v.push_back(x[i]);
		s1.insert({e[i],i});
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	for(int i=0;i<n;++i){
		d[i]=lower_bound(v.begin(),v.end(),x[i])-v.begin();
	}
	rt=new node(0,v.size()-1);
	rt2=new node(0,v.size()-1);
	int ans=0;
	while(!s1.empty()){
		auto[_,i]=*--s1.end();
		s1.erase(--s1.end());
		if(e[i]+x[i]<=rt->qry(0,d[i]))continue;
		if(e[i]-x[i]<=rt2->qry(d[i],v.size()-1))continue;
		++ans;
		rt->up(d[i],e[i]+x[i]);
		rt2->up(d[i],e[i]-x[i]);
	}
	pf("%d\n",ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:39:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  sf("%d",&n);
      |    ^
Main.cpp:41:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   sf("%d%d",&x[i],&e[i]);
      |     ^

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