제출 #1350225

#제출 시각아이디문제언어결과실행 시간메모리
1350225ereringAdvertisement 2 (JOI23_ho_t2)C++20
100 / 100
1320 ms125652 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pb push_back
const int N=5e5+5,MAXN=1e5+5,MAXA=1e6+5,inf=1e18,MOD=998244353;
int seg[N*4][2],offset=1;
void update(int idx,int val,bool type){
    idx+=offset;
    if(!type)seg[idx][type]=min(seg[idx][type],val);
    else seg[idx][type]=max(seg[idx][type],val);
    idx/=2;
    while(idx>0){
        if(!type)seg[idx][type]=min(seg[idx*2][type],seg[idx*2+1][type]);
        else seg[idx][type]=max(seg[idx*2][type],seg[idx*2+1][type]);
        idx/=2;
    }
}
int query(int node,int qlo,int qhi,int lo,int hi,bool type){
    if(lo>=qlo && hi<=qhi)return seg[node][type];
    if(lo>qhi || hi<qlo)return (type?0LL:inf);
    int mid=(lo+hi)/2;
    int x=query(node*2,qlo,qhi,lo,mid,type),y=query(node*2+1,qlo,qhi,mid+1,hi,type);
    if(!type)return min(x,y);
    return max(x,y);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    /*
     * xj<=xi -> xi-xj<=ei-ej -> xi-ei<=xj-ej
     * xj>xi -> xj-xi<=ei-ej -> xj+ej<=xi+ei
     */
    for(int i=0;i<N*4;i++)seg[i][0]=inf;
    int n; cin>>n;
    pair<int,int> p[n];
    set<int> st;
    for(int i=0;i<n;i++){
        cin>>p[i].second>>p[i].first;
        st.insert(p[i].second);
    }
    map<int,int> id,og;
    int cnt=0;
    for(auto i:st){
        og[cnt]=i;
        id[i]=cnt++;
    }
    while(offset<=cnt)offset*=2;
    for(int i=0;i<n;i++)p[i].second=id[p[i].second];
    sort(p,p+n);
    int ans=0;
    for(int i=n-1;i>=0;i--){
        int real=og[p[i].second];
        if(query(1,p[i].second,offset-1,0,offset-1,0)<=real-p[i].first)continue;
        if(real+p[i].first<=query(1,0,p[i].second,0,offset-1,1))continue;
        ans++;
        update(p[i].second,real-p[i].first,0);
        update(p[i].second,real+p[i].first,1);
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...