제출 #1351026

#제출 시각아이디문제언어결과실행 시간메모리
1351026piolkAdvertisement 2 (JOI23_ho_t2)C++20
59 / 100
104 ms11588 KiB
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn=5e5 + 5;
constexpr int inf=2e9+5;
int tree[2][maxn];
int len=1;

int rmax(int v,int cs,int ce,int ls,int le,int t){
    if (cs>=ls && ce<=le) return tree[t][v];
    if (cs>le || ce<ls) return -inf;
    int mid=(cs+ce)/2;
    return max(rmax(2*v,cs,mid,ls,le,t) , rmax(2*v+1,mid+1,ce,ls,le,t));
}

void pmax(int pos,int x,int t){
    pos+=len;
    tree[t][pos]=max(tree[t][pos],x);
    pos/=2;
    for (;pos>=1;pos/=2) tree[t][pos]=max(tree[t][2*pos],tree[t][2*pos+1]);
}

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

    for (int i=0;i<maxn;i++){
        for (int j=0;j<2;j++){
            tree[j][i]=-inf;
        }
    }

    int n;
    cin>>n;

    while (len<n) len<<=1;

    vector<int> X(n),E(n);
    for (int i=0;i<n;i++) cin>>X[i]>>E[i];

    vector<int> v(n);
    for (int i=0;i<n;i++) v[i]=X[i];
    sort(v.begin(),v.end());

    vector<int> ord(n);
    iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int a,int b){
        return E[a]>E[b];
    });

    int ans=0;
    for (int i:ord){
        int x=X[i],e=E[i];
        int compx=lower_bound(v.begin(),v.end(),x)-v.begin();

        if (rmax(1,0,len-1,compx,n,1)>=e-x || rmax(1,0,len-1,0,compx,0)>=e+x){
            //covered
        } else {
            ans++;
            pmax(compx,e-x,1);
            pmax(compx,e+x,0);
        }
    }

    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...