Submission #931519

#	Time	Username	Problem	Language	Result	Execution time	Memory
931519		pcc	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	267 ms	43548 KiB

Main

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


#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
#define int ll

const ll inf = 1e12;
const ll mxn = 5e5+10;
pii arr[mxn];
int brr[mxn];
bitset<mxn> done;
int N;

struct SEG{
	ll seg[mxn*4];
	SEG(){
		fill(seg,seg+mxn*4,-inf);
	}
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now] = max(seg[now],v);
			return;
		}
		int mid = (l+r)>>1;
		if(mid>=s)modify(now*2+1,l,mid,s,e,v);
		if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
	}
	int getval(int now,int l,int r,int p){
		if(l == r)return seg[now];
		int mid = (l+r)>>1;
		if(mid>=p)return max(seg[now],getval(now*2+1,l,mid,p));
		else return max(seg[now],getval(now*2+2,mid+1,r,p));
	}
};

SEG lseg,rseg;

main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1;i<=N;i++){
		cin>>arr[i].fs>>arr[i].sc;
		brr[i] = i;
	}
	sort(arr+1,arr+N+1);
	sort(brr+1,brr+N+1,[](int a,int b){return arr[a].sc>arr[b].sc;});
	int ans = 0;
	for(int i = 1;i<=N;i++){
		int now = brr[i];
		if(lseg.getval(0,1,N,now)>=arr[now].sc-arr[now].fs||rseg.getval(0,1,N,now)>=arr[now].sc+arr[now].fs)continue;
		ans++;
		lseg.modify(0,1,N,1,now,arr[now].sc-arr[now].fs);
		rseg.modify(0,1,N,now,N,arr[now].sc+arr[now].fs);
	}
	cout<<ans;
}

Compilation message (stderr)

Main.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main(){
      | ^~~~

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