Submission #1125592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125592		Warinchai	허수아비 (JOI14_scarecrows)	C++20	0 / 100	165 ms	23288 KiB

scarecrows

#include<bits/stdc++.h>
using namespace std;
int inf=1e9;
struct point{
    int id,x,y;
    point(int _id=0,int _x=0,int _y=0){
        id=_id,x=_x,y=_y;
    }
    friend bool operator<(point a,point b){
        return a.x>b.x;
    }
};
int val[200005];
struct segtree{
    struct node{
        int mn,mn2,mx,mx2,fmn,fmx;
        node(int _mn=inf,int _mn2=inf,int _mx=-inf,int _mx2=-inf,int _fmn=1,int _fmx=1){
            mn=_mn,mn2=_mn2,mx=_mx,mx2=_mx2,fmn=_fmn,fmx=_fmx;
        }
        friend node operator+(node a,node b){
            node c;
            c.mn=min(a.mn,b.mn);
            c.mx=max(a.mx,b.mx);
            c.fmn=(a.mn==b.mn?a.fmn+b.fmn:(a.mn<b.mn?a.fmn:b.fmn));
            c.fmx=(a.mx==b.mx?a.fmx+b.fmx:(a.mx>b.mx?a.fmx:b.fmx));
            c.mn2=(a.mn==b.mn?min(a.mn2,b.mn2):(a.mn<b.mn?min(a.mn2,b.mn):min(a.mn,b.mn2)));
            c.mx2=(a.mx==b.mx?min(a.mx2,b.mx2):(a.mx>b.mx?max(a.mx2,b.mx):max(a.mx,b.mx2)));
            return c;
        }
    };
    node info[800005];
    int ch[800005];
    void push(int st,int en,int i){
        if(!ch[i])return;
        if(ch[i]<=info[i].mn)return;
        info[i].mn=ch[i];
        if(ch[i]>info[i].mx)info[i].mx=ch[i],info[i].mx2=-inf;
        else if(ch[i]>info[i].mx2)info[i].mx2=ch[i];
        if(st!=en){
            ch[i*2]=max(ch[i],ch[i*2]);
            ch[i*2+1]=max(ch[i],ch[i*2+1]);
        }
        ch[i]=0;
    }
    void build(int st,int en,int i){
        if(st==en)return void(info[i]=node(inf,inf,inf,-inf));
        int m=(st+en)/2;
        build(st,m,i*2);
        build(m+1,en,i*2+1);
        info[i]=info[i*2]+info[i*2+1];
    }
    int chmax(int st,int en,int i,int l,int r,int val){
        push(st,en,i);
        if(st>r||en<l||val<=info[i].mn)return 0;
        if(st>=l&&en<=r&&val<info[i].mn2){
            //cerr<<st<<" "<<en<<" "<<info[i].mn<<" "<<info[i].mn2<<":"<<val<<"\n";
            ch[i]=val;
            push(st,en,i);
            return info[i].fmn;
        }
        int m=(st+en)/2;
        int tans=chmax(st,m,i*2,l,r,val)+chmax(m+1,en,i*2+1,l,r,val);
        info[i]=info[i*2]+info[i*2+1];
        return tans;
    }
    void upd(int st,int en,int i,int pos,int val){
        push(st,en,i);
        if(st>pos||en<pos)return;
        if(st==en)return void(info[i]=node(val,inf,val,-inf));
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
    }
}tr;
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    vector<point>p;
    vector<int>y;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        p.push_back(point(i,a+1,b+1));
        y.push_back(b+1);
    }
    sort(p.begin(),p.end());
    sort(y.begin(),y.end());
    int ans=0;
    tr.build(1,n,1);
    for(int i=0;i<p.size();i++){
        int id=lower_bound(y.begin(),y.end(),p[i].y)-y.begin()+1;
        //cerr<<"chmax:\n";
        ans+=tr.chmax(1,n,1,id+1,n,id);
        //cerr<<p[i].id<<" "<<ans<<" "<<id<<"\n";
        tr.upd(1,n,1,id,0);
    }
    cout<<ans;
}

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