제출 #851021

#제출 시각아이디문제언어결과실행 시간메모리
851021arbuzickAdvertisement 2 (JOI23_ho_t2)C++17
59 / 100
2089 ms343748 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; constexpr int R = 1 << 19, inf = 2e9 + 7; set<pair<int, int>> tree[R * 2][2]; void add(int pos, int tp, pair<int, int> val) { for (pos += R; pos > 0; pos /= 2) { tree[pos][tp].insert(val); } } void del(int pos, int tp, pair<int, int> val) { for (pos += R; pos > 0; pos /= 2) { tree[pos][tp].erase(val); } } pair<int, int> get_min(int l, int r, int tp) { l += R; r += R; pair<int, int> ans = {inf, -1}; while (l < r) { if (l & 1) { if (!tree[l][tp].empty()) { ans = min(ans, *tree[l][tp].begin()); } l++; } if (r & 1) { --r; if (!tree[r][tp].empty()) { ans = min(ans, *tree[r][tp].begin()); } } l >>= 1; r >>= 1; } return ans; } pair<int, int> get_max(int l, int r, int tp) { l += R; r += R; pair<int, int> ans = {-inf, -1}; while (l < r) { if (l & 1) { if (!tree[l][tp].empty()) { ans = max(ans, *tree[l][tp].rbegin()); } l++; } if (r & 1) { --r; if (!tree[r][tp].empty()) { ans = max(ans, *tree[r][tp].rbegin()); } } l >>= 1; r >>= 1; } return ans; } void solve() { int n; cin >> n; vector<int> x(n), e(n); vector<pair<int, int>> ord; for (int i = 0; i < n; ++i) { cin >> x[i] >> e[i]; } vector<int> b = x; sort(b.begin(), b.end()); b.resize(unique(b.begin(), b.end()) - b.begin()); for (int i = 0; i < n; ++i) { x[i] = lower_bound(b.begin(), b.end(), x[i]) - b.begin(); add(x[i], 0, {b[x[i]] - e[i], i}); add(x[i], 1, {b[x[i]] + e[i], i}); ord.emplace_back(e[i], i); } sort(ord.rbegin(), ord.rend()); int ans = 0; vector<int> used(n); for (auto [val, ind] : ord) { if (used[ind]) { continue; } used[ind] = 1; ans++; del(x[ind], 0, {b[x[ind]] - e[ind], ind}); del(x[ind], 1, {b[x[ind]] + e[ind], ind}); while (true) { auto p = get_max(0, x[ind] + 1, 0); if (p.second == -1 || p.first < b[x[ind]] - e[ind]) { break; } used[p.second] = 1; del(x[p.second], 0, {b[x[p.second]] - e[p.second], p.second}); del(x[p.second], 1, {b[x[p.second]] + e[p.second], p.second}); } while (true) { auto p = get_min(x[ind], R, 1); if (p.second == -1 || p.first > b[x[ind]] + e[ind]) { break; } used[p.second] = 1; del(x[p.second], 0, {b[x[p.second]] - e[p.second], p.second}); del(x[p.second], 1, {b[x[p.second]] + e[p.second], p.second}); } } cout << ans << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...