Submission #907521

#	Time	Username	Problem	Language	Result	Execution time	Memory
907521		AlphaMale06	Advertisement 2 (JOI23_ho_t2)	C++17	100 / 100	542 ms	66908 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long


void solve(){
	int n;
	cin >> n;
	pair<int, int> a[n];
	for(int i=0; i< n; i++)cin >> a[i].F >> a[i].S;
	sort(a, a+n);
	set<pair<int, int>> st;
	for(int i=0; i< n-1; i++){
		if(a[i].F!=a[i+1].F)st.insert(a[i]);
	}
	st.insert(a[n-1]);
	vector<pair<int, int>> cands;
	for(auto p : st)cands.pb(p);
	st.clear();
	reverse(all(cands));
	for(int i=0; i<cands.size(); i++){
		vector<pair<int, int>> del;
		pair<int, int> p = cands[i];
		for(auto ptr = st.begin(); ptr!=st.upper_bound({cands[i].F+cands[i].S+1, -1}); ptr++){
			del.pb(*ptr);
		}
		for(auto e : del)st.erase(e);
		st.insert({p.F+p.S, i});
	}
	vector<pair<int, int>> ncands;
	for(auto p : st){
		ncands.pb(cands[p.S]);
	}
	cands=ncands;
	sort(all(cands));
	st.clear();
	for(int i=0; i< cands.size(); i++){
		vector<pair<int, int>> del;
		pair<int, int> p = cands[i];
		for(auto ptr = st.lower_bound({cands[i].F-cands[i].S, -1}); ptr!=st.end(); ptr++){
			del.pb(*ptr);
		}
		for(auto e : del)st.erase(e);
		st.insert({p.F-p.S, i});
	}
	cout << st.size() << '\n';
}


signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:30:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0; i<cands.size(); i++){
      |               ~^~~~~~~~~~~~~
Main.cpp:46:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0; i< cands.size(); i++){
      |               ~^~~~~~~~~~~~~~

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