Submission #1294769

#TimeUsernameProblemLanguageResultExecution timeMemory
1294769kaiboyAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
133 ms10148 KiB
#include <algorithm> #include <iostream> using namespace std; const int N = 500000; const int INF = 0x3f3f3f3f; int xx[N], ee[N], ii[N], pp[N], qq[N]; int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n; cin >> n; for (int i = 0; i < n; i++) cin >> xx[i] >> ee[i], ii[i] = i; sort(ii, ii + n, [] (int i, int j) { return xx[i] != xx[j] ? xx[i] < xx[j] : ee[i] < ee[j]; }); int n_ = 1; for (int h = 1; h < n; h++) { int i = ii[h], i_ = ii[n_ - 1]; if (xx[i] > xx[i_] || ee[i] > ee[i_]) ii[n_++] = i; } n = n_; for (int p = -INF, h = 0; h < n; h++) { int i = ii[h]; pp[h] = p, p = max(p, xx[i] + ee[i]); } for (int q = -INF, h = n - 1; h >= 0; h--) { int i = ii[h]; qq[h] = q, q = max(q, ee[i] - xx[i]); } int ans = 0; for (int h = 0; h < n; h++) { int i = ii[h]; if (xx[i] + ee[i] > pp[h] && ee[i] - xx[i] > qq[h]) ans++; } 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...