Submission #938363

#	Time	Username	Problem	Language	Result	Execution time	Memory
938363		tw20000807	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	1676 ms	497156 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define X first
#define Y second
#define see(x) cerr << #x << " " << x << "\n";
using namespace std;
struct TREE{
	struct node{
		node *l, *r;
		int val;
		node(){
			l = r = nullptr;
			val = -2e9;
		}
	}*root;
	TREE(){
		root = nullptr;
	}
	int query(int qx, node *n, int l = 1, int r = 1e9){
		if(!n) return -2e9;
		int mid = l + r >> 1;
		if(qx <= mid) return max(n->val, query(qx, n->l, l, mid));
		else return max(n->val, query(qx, n->r, mid + 1, r));
	}
	void modify(int ql, int qr, int qv, node *&n, int l = 1, int r = 1e9){
		if(!n) n = new node;
		if(ql <= l && r <= qr){
			
			n->val = max(n->val, qv);
			
			return;
		}
		int mid = l + r >> 1;
		if(ql <= mid) modify(ql, qr, qv, n->l, l, mid);
		if(qr > mid) modify(ql, qr, qv, n->r, mid + 1, r);
	}
};
signed main(){
	int n;
	cin >> n;
	vector< pii > v(n);
	TREE l, r;
	priority_queue< pii > pq;
	for(int i = 0; i < n; ++i){
		cin >> v[i].X >> v[i].Y;
		pq.push({v[i].Y, i});
	}
	int ans = 0;
	while(!pq.empty()){
		int id = pq.top().Y; pq.pop();
		if(l.query(v[id].X, l.root) >= v[id].Y - v[id].X){
			continue;
		}
		if(r.query(v[id].X, r.root) >= v[id].Y + v[id].X){
			continue;
		}
		++ans;
		l.modify(1, v[id].X, v[id].Y - v[id].X, l.root);
		r.modify(v[id].X, 1e9, v[id].Y + v[id].X, r.root);
	}
	cout << ans << "\n";
}
/*

|Xi - Xj| <= Ei - Ej

if(Xi > Xj) Ei - Xi >= Ej - Xj
if(Xi < Xj) Ei + Xi >= Ej + Xj



*/

Compilation message (stderr)

Main.cpp: In member function 'long long int TREE::query(long long int, TREE::node*, long long int, long long int)':
Main.cpp:22:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In member function 'void TREE::modify(long long int, long long int, long long int, TREE::node*&, long long int, long long int)':
Main.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int mid = l + r >> 1;
      |             ~~^~~

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