Submission #1201898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201898		Warinchai	허수아비 (JOI14_scarecrows)	C++20	100 / 100	284 ms	25960 KiB

scarecrows

#include<bits/stdc++.h>
#define int long long
using namespace std;
//int mn[200005];
int inf=1e9+5;
vector<pair<int,int>>v;
vector<int>val;
int ans=0;
struct node{
    int mx,mx2,fmx;
    node(int _mx=-inf,int _mx2=-inf,int _fmx=1){
        mx=_mx,mx2=_mx2,fmx=_fmx;
    }
    friend node operator+(node a,node b){
        node c;
        if(a.mx>b.mx){
            c.mx=a.mx;
            c.fmx=a.fmx;
            c.mx2=max(a.mx2,b.mx);
        }else if(a.mx<b.mx){
            c.mx=b.mx;
            c.fmx=b.fmx;
            c.mx2=max(a.mx,b.mx2);
        }else{
            c.mx=a.mx;
            c.fmx=a.fmx+b.fmx;
            c.mx2=max(a.mx2,b.mx2);
        }
        return c;
    }
};
struct segtree_beats{
    node info[800005];
    void pushmx(int st,int en,int i,int mx){
        if(mx>info[i].mx)return;
        info[i].mx=mx;
    }
    void push(int st,int en,int i){
        int m=(st+en)/2;
        if(st==en)return;
        pushmx(st,m,i*2,info[i].mx);
        pushmx(m+1,en,i*2+1,info[i].mx);
    }
    void chmin(int st,int en,int i,int l,int r,int val){
        if(st>r||en<l||info[i].mx<val)return;
        if(st>=l&&en<=r&&val>info[i].mx2){
            //cerr<<st<<" "<<en<<" "<<info[i].mx<<"\n";
            return ans+=info[i].fmx,pushmx(st,en,i,val);
        }
        push(st,en,i);
        int m=(st+en)/2;
        chmin(st,m,i*2,l,r,val);
        chmin(m+1,en,i*2+1,l,r,val);
        info[i]=info[i*2]+info[i*2+1];
    }
    void upd(int st,int en,int i,int pos,int val){
        push(st,en,i);
        if(st==en){
            //cerr<<"upd:"<<st<<" "<<val<<"\n";
            return void(info[i].mx=val);
        }
        int m=(st+en)/2;
        if(pos<=m)upd(st,m,i*2,pos,val);
        else upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
    }
}tr;
int32_t main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;cin>>x>>y;
        v.push_back({x,y});
        val.push_back(y);
    }
    sort(val.begin(),val.end());
    sort(v.begin(),v.end());
    //for(int i=0;i<n;i++)mn[i]=inf;
    for(int i=0;i<n;i++){
        v[i].second=lower_bound(val.begin(),val.end(),v[i].second)-val.begin()+1;
    }
    for(int i=0;i<n;i++){
        //cerr<<"i:"<<v[i].second<<"\n";
        tr.chmin(1,n,1,1,v[i].second-1,v[i].second);
        tr.upd(1,n,1,v[i].second,inf);
        //cerr<<ans<<"\n";
    }
    cout<<ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85