Submission #884645

#	Time	Username	Problem	Language	Result	Execution time	Memory
884645		salyg1n	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	470 ms	51196 KiB

Main

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define mp make_pair
#define uset unordered_set
#define umap unordered_map
#define mset multiset
#define lb lower_bound
#define ub upper_bound
#define int long long

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef set<int> si;
typedef vector<si> vsi;
typedef mset<int> msi;
typedef vector<msi> vmsi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<vpi> vvpi;
typedef set<pi> spi;
typedef mset<pi> mspi;
typedef vector<spi> vspi;
typedef tuple<int, int, int> ti;
typedef vector<ti> vti;
typedef vector<vti> vvti;
typedef set<ti> sti;
typedef mset<ti> msti;
typedef vector<sti> vsti;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef map<int, int> mii;

mt19937 rnd(228);

template<typename t> bool minravno(t& a, t b) {
	if (b < a) {
		a = b;
		return true;
	}
	return false;
}
template<typename t> bool maxravno(t& a, t b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}
template<typename t> void input(t& a, int i = 0, int j = -1) {
	if (j == -1)
		j = a.size() - 1;
	for (int k = i; k <= j; ++k) {
		cin >> a[k];
	}
}

const int MAXN = 2e5 + 10, MAX = 1e4 + 10, INF = 1e18, MOD = 998244353;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	vpi a = {{0, 0}};
	mii m;
	for (int i = 1; i <= n; ++i) {
		int x, y;
		cin >> x >> y;
		maxravno(m[x], y);
	}
	for (auto[x, y] : m)
		a.push_back({x, y});
	n = a.size() - 1;
	vb l(n + 1, false), r(n + 1, false);
	int mx = 0;
	for (int i = 1; i <= n; ++i) {
		if (!maxravno(mx, a[i].first + a[i].second))
			l[i] = true;
	}
	mx = -INF;
	for (int i = n; i >= 1; --i) {
		if (!maxravno(mx, -a[i].first + a[i].second))
			r[i] = true;
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		if (!l[i] && !r[i])
			ans++;
	cout << ans;


	return 0;
}

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