Submission #762123

#	Time	Username	Problem	Language	Result	Execution time	Memory
762123		IvanJ	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	1210 ms	74964 KiB

Main

#include<bits/stdc++.h>

#define x first
#define y second
#define pb push_back
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 5e5 + 5;

int n, pot = 1;
int x[maxn];
int e[maxn];
int T1[maxn * 4], T2[maxn * 4];
map<int, int> pos;
vector<ii> v;

void update1(int x, int v) {
	x += pot;
	T1[x] = min(T1[x], v);
	x >>= 1;
	while(x > 0) 
		T1[x] = min(T1[x * 2], T1[x * 2 + 1]), x >>= 1;	
}

void update2(int x, int v) {
	x += pot;
	T2[x] = max(T2[x], v);
	x >>= 1;
	while(x > 0) 
		T2[x] = max(T2[x * 2], T2[x * 2 + 1]), x >>= 1;	
}

int query1(int x, int lo, int hi, int a, int b) {
	if(hi < a || b < lo) return 2e9 + 1;
	if(a <= lo && hi <= b) return T1[x];
	int mid = (lo + hi) / 2;
	int L = query1(x * 2, lo, mid, a, b);
	int R = query1(x * 2 + 1, mid + 1, hi, a, b);
	return min(L, R);	
}

int query2(int x, int lo, int hi, int a, int b) {
	if(hi < a || b < lo) return -2e9 - 1;
	if(a <= lo && hi <= b) return T2[x];
	int mid = (lo + hi) / 2;
	int L = query2(x * 2, lo, mid, a, b);
	int R = query2(x * 2 + 1, mid + 1, hi, a, b);
	return max(L, R);	
}

int check(int i, int j) {
	return abs(x[i] - x[j]) <= e[i] - e[j];	
}

int main() {
	scanf("%d", &n);
	for(int i = 0;i < n;i++) 
		scanf("%d%d", x + i, e + i);
	while(pot < n) pot <<= 1;
	for(int i = 1;i < (pot << 1);i++) 
		T1[i] = 2e9 + 1, T2[i] = -2e9 - 1;
	
	for(int i = 0;i < n;i++)
		v.pb({e[i], x[i]});
	sort(all(v));
	reverse(all(v));
	
	set<int> s;
	for(int i = 0;i < n;i++) 
		s.insert(x[i]);
	vector<int> v1(all(s));
	int m = (int)v1.size();
	for(int i = 0;i < m;i++) 
		pos[v1[i]] = i;
	
	int ans = 0;
	for(ii p : v) {
		int flag = 1;
		
		int A = query1(1, 0, pot - 1, pos[p.y], m - 1);
		int B = query2(1, 0, pot - 1, 0, pos[p.y]);
		if(p.y - p.x >= A) flag = 0;
		if(p.y + p.x <= B) flag = 0;
		ans += flag;
		if(flag) {
			update1(pos[p.y], p.y - p.x);
			update2(pos[p.y], p.y + p.x);
		}
	}
	
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d%d", x + i, e + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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