Submission #1356184

#TimeUsernameProblemLanguageResultExecution timeMemory
1356184nathlol2Advertisement 2 (JOI23_ho_t2)C++20
100 / 100
529 ms383180 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, INF = 1e9;
int n, ans;
pair<int, int> a[N];
//too lazy to do coord compression
struct sparseseg{
    struct node{
        int v;
        node *l, *r;
        node(int v):v(v), l(0), r(0){}
    };
    typedef node* pnode;
    pnode rt = 0;
    void upd(pnode &k, int l, int r, int pos, int x){
        if(!k) k = new node(0);
        if(l == r) return k->v = x, void();
        int md = (l + r) / 2;
        if(pos <= md) upd(k->l, l, md, pos, x);
        else upd(k->r, md + 1, r, pos, x);
        k->v = max(k->l ? k->l->v : -INF, k->r ? k->r->v : -INF);
    }
    int qry(pnode k, int l, int r, int ql, int qr){
        if(!k || qr < l || r < ql) return -INF;
        if(ql <= l && r <= qr) return k->v;
        int md = (l + r) / 2;
        return max(qry(k->l, l, md, ql, qr), qry(k->r, md + 1, r, ql, qr));
    }
}s1, s2;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1;i<=n;i++) cin >> a[i].second >> a[i].first;
    sort(a + 1, a + n + 1, greater<pair<int, int>>());
    for(int i = 1;i<=n;i++){
        if(s1.qry(s1.rt, 1, INF, 1, a[i].second) >= a[i].first + a[i].second || s2.qry(s2.rt, 1, INF, a[i].second, INF) >= a[i].first - a[i].second) continue;
        ++ans;
        s1.upd(s1.rt, 1, INF, a[i].second, a[i].first + a[i].second);
        s2.upd(s2.rt, 1, INF, a[i].second, a[i].first - a[i].second);
    }
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...