제출 #1322678

#제출 시각아이디문제언어결과실행 시간메모리
1322678Hamed_GhaffariAdvertisement 2 (JOI23_ho_t2)C++20
0 / 100
7 ms15928 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(a, a+n);
    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...