Submission #1235864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235864		AlgorithmWarrior	Advertisement 2 (JOI23_ho_t2)	C++20	100 / 100	956 ms	36028 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int n;
int const NMAX=500005;
struct point{
    int x,y;
    bool operator<(point ot){
        return y>ot.y;
    }
}pct[NMAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>pct[i].x>>pct[i].y;
    sort(pct+1,pct+n+1);
}

map<int,int>nrm;
int norm_total;

void normalize(){
    int i;
    for(i=1;i<=n;++i)
        nrm[pct[i].x]=0;
    for(auto &[val,new_val] : nrm)
        new_val=++norm_total;
}

int const INF=1e9;

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

struct segment_tree{
    int v[4*NMAX];
    void init(int nod,int st,int dr){
        v[nod]=-INF;
        if(st<dr){
            int mij=(st+dr)/2;
            init(2*nod,st,mij);
            init(2*nod+1,mij+1,dr);
        }
    }
    void update(int nod,int st,int dr,int pos,int val){
        maxself(v[nod],val);
        if(st<dr){
            int mij=(st+dr)/2;
            if(pos<=mij)
                update(2*nod,st,mij,pos,val);
            else
                update(2*nod+1,mij+1,dr,pos,val);
        }
    }
    int query(int nod,int st,int dr,int a,int b){
        if(a<=st && dr<=b)
            return v[nod];
        int mij=(st+dr)/2;
        int ans=-INF;
        if(a<=mij)
            maxself(ans,query(2*nod,st,mij,a,b));
        if(b>mij)
            maxself(ans,query(2*nod+1,mij+1,dr,a,b));
        return ans;
    }
}aint1,aint2;

int solve(){
    int cnt=0;
    aint1.init(1,1,norm_total);
    aint2.init(1,1,norm_total);
    int i;
    for(i=1;i<=n;++i){
        auto [x,y]=pct[i];
        bool activ=0;
        int mxm1=aint1.query(1,1,norm_total,nrm[x],norm_total);
        if(y-x<=mxm1)
            activ=1;
        int mxm2=aint2.query(1,1,norm_total,1,nrm[x]);
        if(x+y<=mxm2)
            activ=1;
        if(!activ){
            ++cnt;
            aint1.update(1,1,norm_total,nrm[x],y-x);
            aint2.update(1,1,norm_total,nrm[x],x+y);
        }
    }
    return cnt;
}

int main()
{
    read();
    normalize();
    cout<<solve();
    return 0;
}

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