제출 #999000

#제출 시각아이디문제언어결과실행 시간메모리
999000Angus_YeungAdvertisement 2 (JOI23_ho_t2)C++17
100 / 100
543 ms77136 KiB
#include <bits/stdc++.h> #define x first #define e second #define pii pair<ll, ll> typedef long long ll; const ll MOD = 1000000007LL; const ll INF = 1e15; using namespace std; ll n, x, e, k, ans; pii a[500010]; bool vis[500010]; map<ll, ll> mp; set<pii> q; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> x >> e; mp[x] = max(mp[x], e); } k = 0; for (auto i: mp) { k++; a[k] = i; vis[k] = 0; } while (q.size()) q.erase(q.begin()); for (int i = 1; i <= k; i++) { while (q.size() && a[i].x - a[i].e <= q.rbegin()->first) { vis[q.rbegin()->second] = 1; q.erase(*q.rbegin()); } q.insert({a[i].x - a[i].e, i}); } while (q.size()) q.erase(q.begin()); for (int i = k; i >= 1; i--) { while (q.size() && a[i].x + a[i].e >= q.begin()->first) { vis[q.begin()->second] = 1; q.erase(*q.begin()); } q.insert({a[i].x + a[i].e, i}); } ans = 0; for (int i = 1; i <= k; i++) { ans += !vis[i]; } cout << ans << "\n"; return 0; } /* xi - ei <= xj - ej xi + ei >= xj + ej */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...