Submission #1249704

#TimeUsernameProblemLanguageResultExecution timeMemory
1249704norman165Advertisement 2 (JOI23_ho_t2)C++20
33 / 100
272 ms47532 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define int long long #define yes() cout << "YES\n" #define no() cout << "NO\n" using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; const int inf = 1e18; const int mod = 1e9 + 7; const int maxn = 1e7 + 5e6; const int mod1 = 998244353; const int mod2 = 1e18 + 1; const int mod3 = 1e9 + 9; const int mod4 = 333333333; const int mod5 = 200000; const int mod6 = 10007; const int k = 300; const int w = 1e5; const ld EPS = 1e-8; int LOG = 30; struct segTree { vector<int> t; int n; segTree(int x) { n = x; t.resize(4 * n, -inf); } void upd(int v, int l, int r, int idx, int val) { if (r - l == 1) { t[v] = val; return; } int m = (l + r) / 2; if (idx < m) upd(2 * v, l, m, idx, val); else upd(2 * v + 1, m, r, idx, val); t[v] = max(t[2 * v], t[2 * v + 1]); } void upd(int idx, int val) { upd(1, 0, n, idx, val); } int get(int v, int l, int r, int ql, int qr) { if (l >= qr || r <= ql) return -inf; if (ql <= l && r <= qr) return t[v]; int m = (l + r) / 2; return max(get(2 * v, l, m, ql, qr), get(2 * v + 1, m, r, ql, qr)); } int get(int ql, int qr) { return get(1, 0, n, ql, qr); } }; void solve() { int n; cin >> n; vector<pair<int, int>> a(n); for (auto& i : a) cin >> i.first >> i.second; sort(all(a), [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second || (a.second == b.second && a.first < b.first); }); vector<int> b; for (int i = 0; i < n; i++) b.push_back(a[i].first); sort(all(b)); b.resize(unique(all(b)) - b.begin()); for (int i = 0; i < n; i++) a[i].first = lower_bound(all(b), a[i].first) - b.begin(); segTree st1(n), st2(n); int ans = n; vector<int> cnt(n); for (int i = n - 1; i >= 0; i--) { int val = a[i].first; if (b[val] + a[i].second <= st1.get(0, val)) cnt[i] = 1; if (a[i].second - b[val] <= st2.get(val, n)) cnt[i] = 1; st1.upd(val, b[val] + a[i].second); st2.upd(val, a[i].second - b[val]); } // for (int i = 0; i < n; i++) { // for (int j = i + 1; j < n; j++) { // if (a[i].first >= a[j].first) { // if (a[i].first + a[i].second <= a[j].first + a[j].second) cnt[i] = 1; // } else { // if (a[i].second - a[i].first <= a[j].second - a[j].first) cnt[i] = 1; // } // } // } cout << ans - accumulate(all(cnt), 0ll) << "\n"; } signed main() { // cout.precision(16); ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...