Submission #885425

#TimeUsernameProblemLanguageResultExecution timeMemory
885425juliany2Advertisement 2 (JOI23_ho_t2)C++17
10 / 100
309 ms23920 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define all(x) (x).begin(), (x).end() template<class T> struct ST { static constexpr T ID = {(int) -1e9, (int) -1e9}; // or whatever ID inline T comb(T a, T b) { return max(a, b); } // or whatever function int sz; vector<T> t; void init(int _sz, T val = ID) { t.assign((sz = _sz) * 2, ID); } void init(vector<T> &v) { t.resize((sz = v.size()) * 2); for (int i = 0; i < sz; ++i) t[i + sz] = v[i]; for (int i = sz - 1; i; --i) t[i] = comb(t[i * 2], t[(i * 2) | 1]); } void upd(int i, T x) { for (t[i + sz] = max(t[i + sz], x), i += sz; i > 1; i >>= 1) t[i >> 1] = comb(t[i], t[i ^ 1]); } T query(int l, int r) { T ql = ID, qr = ID; for (l += sz, r += sz + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) ql = comb(ql, t[l++]); if (r & 1) qr = comb(t[--r], qr); } return comb(ql, qr); } }; int main() { cin.tie(0)->sync_with_stdio(false); int n; cin >> n; vector<array<int, 2>> a(n); vector<int> pos; for (auto &[x, e] : a) { cin >> x >> e; pos.push_back(x); } sort(all(a)); sort(all(pos)); a.erase(unique(all(a)), a.end()); pos.erase(unique(all(pos)), pos.end()); auto get = [&](int x) { return lower_bound(all(pos), x) - pos.begin(); }; ST<array<int, 2>> st; st.init(n + 1); sort(all(a), [&](array<int, 2> &x, array<int, 2> &y) { return x[1] > y[1]; }); int ans = a.size(); for (auto &[x, e] : a) { int i = get(x); if (st.query(i, n)[0] >= e - x || st.query(0, i)[1] >= e + x) ans--; st.upd(i, {e - x, e + x}); } cout << ans << '\n'; 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...