제출 #1322670

#제출 시각아이디문제언어결과실행 시간메모리
1322670Hamed_GhaffariAdvertisement 2 (JOI23_ho_t2)C++20
0 / 100
24 ms17724 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; #define X first #define Y second #define lc id<<1 #define rc lc|1 #define mid ((l+r)>>1) #define all(x) x.begin(), x.end() #define SZ(x) int(x.size()) const int MXN = 5e5+5; int N; struct Seg { int seg[MXN<<2]; Seg() { fill(seg, seg+(MXN<<2), -2e9-7); } void upd(int p, int x, int l=0, int r=N, int id=1) { seg[id] = max(seg[id], x); if(r-l == 1) return; p<mid ? upd(p, x, l, mid, lc) : upd(p, x, mid, r, rc); } int get(int s, int e, int l=0, int r=N, int id=1) { if(s>=r || l>=e) return -2e9-7; if(s<=l && r<=e) return seg[id]; return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc)); } } seg[2]; vector<int> cmp; int GI(int x) { return lower_bound(all(cmp), x)-cmp.begin(); } int n, ans; pii a[MXN]; int32_t main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> n; for(int i=0; i<n; i++) cin >> a[i].Y >> a[i].X, cmp.push_back(a[i].X); sort(all(cmp)); cmp.resize(unique(all(cmp))-cmp.begin()); N = SZ(cmp); for(int i=n-1; i>=0; i--) { // x[j]-x[i] <= E[j]-E[i] -> E[i]-x[i] <= E[j]-x[j] // x[i]-x[j] <= E[j]-E[i] -> E[i]+x[i] <= E[j]+x[j] int pos = GI(a[i].X); if(a[i].Y-a[i].X > seg[0].get(pos, N) && a[i].Y+a[i].X > seg[1].get(0, pos)) { ans++; seg[0].upd(pos, a[i].Y-a[i].X); seg[1].upd(pos, a[i].Y+a[i].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...