Submission #1214047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214047		minhpk	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	422 ms	28628 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
     int x,e,id;
};
node z[1000000];
bool cmp(node a,node b){
    return a.x<b.x;
}
bool cmp1(node a,node b){
    return a.e>b.e;
}
int f[4000000];
int f1[4000000];
void build(int id,int l,int r){
    if (l==r){
        f[id]=1e16;
        return;
    }
    int mid =(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    f[id]=min(f[id*2],f[id*2+1]);
}

void build1(int id,int l,int r){
    if (l==r){
        f1[id]=-1e16;
        return;
    }
    int mid =(l+r)/2;
    build1(id*2,l,mid);
    build1(id*2+1,mid+1,r);
    f1[id]=max(f1[id*2],f1[id*2+1]);
}

void update(int id,int l,int r,int pos,int val){
    if (l==r){
        f[id]=val;
        return;
    }
    int mid =(l+r)/2;
    if (pos<=mid){
        update(id*2,l,mid,pos,val);
    }else{
        update(id*2+1,mid+1,r,pos,val);
    }
    f[id]=min(f[id*2],f[id*2+1]);
}

void update1(int id,int l,int r,int pos,int val){
    if (l==r){
        f1[id]=val;
        return;
    }
    int mid =(l+r)/2;
    if (pos<=mid){
        update1(id*2,l,mid,pos,val);
    }else{
        update1(id*2+1,mid+1,r,pos,val);
    }
    f1[id]=max(f1[id*2],f1[id*2+1]);
}

int get(int id,int l,int r,int x,int y){
   if (x>r || y<l){
       return 1e16;
   }
   if (l>=x && y>=r){
       return f[id];
   }
   int mid =(l+r)/2;
   return min(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));

}

int get1(int id,int l,int r,int x,int y){
   if (x>r || y<l){
       return -1e16;
   }
   if (l>=x && y>=r){
       return f1[id];
   }
   int mid =(l+r)/2;
   return max(get1(id*2,l,mid,x,y),get1(id*2+1,mid+1,r,x,y));

}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a;
    cin >> a;
    for (int i=1;i<=a;i++){
        cin >> z[i].x >> z[i].e;
    }
    sort(z+1,z+1+a,cmp);
    for (int i=1;i<=a;i++){
        z[i].id=i;
    }
    sort(z+1,z+1+a,cmp1);
    build(1,1,a);
    build1(1,1,a);
    int ans=0;
    for (int i=1;i<=a;i++){
         bool check=false;
         int pre1=get1(1,1,a,1,z[i].id);
         if (pre1>=z[i].x+z[i].e){
            check=true;
         }
        // cout << z[i].x+z[i].e << " " << pre1 << "\n";
         if (!check){
            int pre2=get(1,1,a,z[i].id,a);
            if (pre2<=z[i].x-z[i].e){
               check=true;
            }
         }
         if (!check){
            ans++;
         }
         update(1,1,a,z[i].id,z[i].x-z[i].e);
         update1(1,1,a,z[i].id,z[i].x+z[i].e);
    }
    cout << ans;

    return 0;
}

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