Submission #1187195

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187195		Dedibeat	Advertisement 2 (JOI23_ho_t2)	C++20	0 / 100	126 ms	8216 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> t;
void upd(int v, int tl, int tr, int pos, int val)
{
	if(tl == tr) t[v] += val;
	else {
		int tm = (tl + tr) / 2;
		if(pos <= tm) upd(2 * v, tl, tm, pos, val);
		else upd(2 * v + 1, tm + 1, tr, pos, val);
		t[v] = t[2 * v] + t[2 * v + 1];
	}
}
int get(int v, int tl, int tr, int l, int r)
{
	if(l > r) return 0;
	if(tl == l && tr == r) return t[v];
	else {
		int tm = (tl + tr) / 2;
		return get(2 * v, tl, tm, l, min(r, tm)) + 
				get(2 * v + 1, tm + 1, tr, max(l, tm + 1), r);
	}
}
void comp(vector<int> &v)
{
	map<int, int> mp;
	for(int &x : v) mp[x] = 1, cout << x << "\n";
	int cnt = 0;
	for(auto &[f, s] : mp) s = cnt++;
	for(int &x : v) x = mp[x], cout << x << "\n";
}
int main()
{
	int n;
	cin >> n;
	vector<pair<int, int>> v(n);
	for(auto &[x, y] : v) cin >> x >> y;
	sort(v.begin(), v.end());
	vector<int> vec1, vec2;
	for(auto &[x, y] : v)
	{
		vec1.push_back(x - y);
		vec2.push_back(x + y);
	}
	
	set<int> st;
	vector<int> cnt(n, 0);
	for(int i = 0; i < n; i++)
	{
		auto it = st.lower_bound(vec2[i]);
		if(it != st.end()) cnt[i] = 1;
		st.insert(vec2[i]);
	}
	
	st.clear();
	
	for(int i = n - 1; i >= 0; i--)
	{
		auto it = st.lower_bound(-vec1[i]);
		if(it != st.end()) cnt[i] = 1;
		st.insert(-vec1[i]);
	}
	
	int ans = 0;
	for(int i = 0; i < n; i++)
		if(cnt[i] == 1) ans++;
	cout << ans;
}

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