Submission #1085465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085465		I_am_Polish_Girl	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	504 ms	57792 KiB

Main

#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;

#define int long long

typedef long long ll;
typedef long double ld;

int log_ = 21;
int inf = 4000000007000000007;

long long mod = 998244353;

int p = 499;

int NADIYA = 39;

struct segment_tree
{
	vector <int> tree;

	int s = 1;

	void init(int n)
	{
		s = 1;

		while (s < n)
			s *= 2;

		tree.resize(2 * s , -inf);
	}

	void modif(int ind, int l, int r , int indx , int x)
	{
		if(r - l == 1)
		{
			tree[ind] = max(tree[ind], x);
			return;
		}

		int m = (l + r) / 2;

		if (indx < m)
			modif(ind * 2 + 1, l, m, indx, x);
		else
			modif(ind * 2 + 2, m, r, indx, x);

		tree[ind] = max(tree[ind * 2 + 1], tree[ind * 2 + 2]);
	}

	void modif(int indx, int x)
	{
		modif(0, 0, s, indx, x);
	}

	int get(int ind, int l, int r, int lx, int rx)
	{
		if ((lx <= l) and (r <= rx))
		{
			return tree[ind];
		}

		if ((rx <= l) or (r <= lx))
			return -inf;

		int m = (l + r) / 2;

		int g1 = get(ind * 2 + 1, l, m, lx, rx);
		int g2 = get(ind * 2 + 2, m, r, lx, rx);

		return max(g1, g2);
	}

	int get(int lx, int rx)
	{
		return get(0, 0, s, lx, rx);
	}

};

bool cmp(pair <int, int> a, pair <int, int> b)
{
	if (a.second > b.second)
	{
		return true;
	}

	return false;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	vector <pair <int, int>> vp(n);

	for (int i = 0; i < n; i++)
		cin >> vp[i].first >> vp[i].second;

	sort(vp.begin(), vp.end(), cmp);

	vector <pair <int, int>> vp_;

	for (int i = 0; i < n; i++)
	{
		vp_.push_back({ vp[i].first , i });
	}

	sort(vp_.begin(), vp_.end());

	int c = 0;

	vector <int> x(n);

	for (int i = 0; i < n; i++)
	{
		if (i > 0)
		{
			if (vp_[i - 1].first != vp_[i].first)
				c++;
		}

		x[vp_[i].second] = c;
	}

	c++;

	vector <int> y(c);
	for (int i = 0; i < n; i++)
	{
		y[x[i]] = vp[i].first;
	}

	vector <int> p1(c);

	for (int i = 0; i < c; i++)
	{
		p1[i] = y[i];
	}

	vector <int> p2(c);

	for (int i = 0; i < c; i++)
	{
		p2[i] = -y[i];
	}

	segment_tree st1;
	segment_tree st2;

	st1.init(c);
	st2.init(c);

	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		int p = vp[i].first;
		int e = vp[i].second;

		int g = st1.get(0, x[i] + 1);
		
		g -= p1[x[i]];

		if (g >= e)
		{
			continue;
		}

		g = st2.get(x[i] , c);

		g -= p2[x[i]];

		if (g >= e)
		{
			continue;
		}

		ans++;

		st1.modif(x[i], e + p1[x[i]]);
		st2.modif(x[i], e + p2[x[i]]);
	}

	cout << ans;
}

/*5
1 2 1
2 3 1
2 4 1
1 5 4
*/

Compilation message (stderr)

Main.cpp:1: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    1 | #pragma target("arch=icelake-server")
      | 
Main.cpp: In function 'int main()':
Main.cpp:180:7: warning: unused variable 'p' [-Wunused-variable]
  180 |   int p = vp[i].first;
      |       ^

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