Submission #1235988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235988		wetsponge	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	1920 ms	136484 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define mod 1000000007
const int N=(1ll<<20);
array <int,2> Tree[2][N*2+5];
int n,E[500001],X[500001],inf=1e17;
map <int,int> key;
set <int> st;
void update(int i,int u,int val,int idx){
    i+=N;
    Tree[u][i]={val,idx};
    i/=2;
    while(i!=0){
        Tree[u][i]=max(Tree[u][i*2],Tree[u][i*2+1]);
        i/=2;
    }
    return;
}
array <int,2> solve(int l1,int r1,int i,int l,int r,int u){
    if(l1>r||l>r1) return {-inf,-1};
    if(l<=l1&&r1<=r) return Tree[u][i];
    return max(solve(l1,(l1+r1)/2,i*2,l,r,u),solve((l1+r1)/2+1,r1,i*2+1,l,r,u));
}
bool cover(int i,int j){
    if(i==-1) return 0;
    return ((E[i]-E[j])>=abs(X[i]-X[j]));
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    vector <array<int,2>> v;
    for(int i=0;i<=N*2+4;i++) Tree[0][i]=Tree[1][i]={-inf,-1};
    for(int i=1;i<=n;i++){
        cin>>X[i]>>E[i];
        st.insert(X[i]);
        v.push_back({E[i],i});
    }
    int comp=1;
    for(int i:st) key[i]=comp++;
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    int ans=0;
    for(auto [val,i]:v){
        int idx1=solve(0,N-1,1,key[X[i]],n,0)[1],idx2=solve(0,N-1,1,1,key[X[i]],1)[1];
        if(cover(idx1,i)==1||cover(idx2,i)==1) continue;
        ans++;
        update(key[X[i]],0,E[i]-X[i],i);
        update(key[X[i]],1,E[i]+X[i],i);
    }
    cout<<ans<<endl;
}
//179276892

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