Submission #1076531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076531		dwuy	Advertisement 2 (JOI23_ho_t2)	C++14	100 / 100	417 ms	33984 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int INF = 2e9 + 5;

struct SMT{
    int n;
    vector<int> tree;

    SMT(int n = 0){
        this->n = n;
        this->tree.assign(n<<2|3, INF);
    }
    
    void update(int pos, int val){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1|1;            
        }
        tree[id] = val;
        for(id>>=1; id; id>>=1) tree[id] = min(tree[id<<1], tree[id<<1|1]);
    }

    void get(int l, int r, int id, const int &pos, const int &val, vector<int> &vt){
        if(tree[id] > val || l >= pos) return;
        if(l == r){
            vt.push_back(l);
            return;
        }
        int mid = (l + r)>>1;
        get(l, mid, id<<1, pos, val, vt);
        get(mid + 1, r, id<<1|1, pos, val, vt);
    }

    void get(int pos, int val, vector<int> &vt){
        get(1, n, 1, pos, val, vt);
    }

    void rget(int l, int r, int id, const int &pos, const int &val, vector<int> &vt){
        if(tree[id] > val || r <= pos) return;
        if(l == r){
            vt.push_back(l);
            return;
        }
        int mid = (l + r)>>1;
        rget(l, mid, id<<1, pos, val, vt);
        rget(mid + 1, r, id<<1|1, pos, val, vt);
    }

    void rget(int pos, int val, vector<int> &vt){
        rget(1, n, 1, pos, val, vt);
    }
};

const int MX = 500005;
int n;
pii a[MX];
int b[MX];
bitset<MX> used = 0;

void nhap(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
    }
}

void solve(){
    for(int i=1; i<=n; i++) b[i] = i;
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n, [&](const int &x, const int &y) -> bool {return a[x].se > a[y].se;});
    SMT pf(n), sf(n);
    for(int i=1; i<=n; i++){
        pf.update(i, a[i].se - a[i].fi);
        sf.update(i, a[i].fi + a[i].se);
    }   
    int ans = 0;
    for(int j=1; j<=n; j++) if(!used[b[j]]){
        int i = b[j];
        ans++;
        used[i] = 1;
        pf.update(i, INF);
        sf.update(i, INF);
        vector<int> vt;
        pf.get(i, a[i].se - a[i].fi, vt);
        sf.rget(i, a[i].fi + a[i].se, vt);
        for(int x: vt){
            pf.update(x, INF);
            sf.update(x, INF);
            used[x] = 1;
        }
    }
    cout << ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 

    nhap();
    solve();

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31