Submission #12064

#	Time	Username	Problem	Language	Result	Execution time	Memory
12064		dohyun0324	허수아비 (JOI14_scarecrows)	C++98	15 / 100	148 ms	14248 KiB

scarecrows

#include<stdio.h>
#include<algorithm>
using namespace std;
int s,c,w,n,w1,w2,top,arr1[200010],arr2[200010],tree[200010],go[200010],cnt[200010];
struct data{
    int x,y;
    bool operator<(const data&r)const{
        return x<r.x;
    }
}a[200010];
struct data5{
    int x,y;
}a2[200010];
struct data2{
    int x,y;
    bool operator<(const data2&r)const{
        return y>r.y;
    }
}b[200010];
struct data3{
    int x,pos;
}st[200010];
struct data4{
    int x,y;
    bool operator<(const data4&r)const{
        return y<r.y;
    }
}p[200010];
void dfs(int x)
{
    if(tree[x]==0){s=x; return;}
    dfs(tree[x]);
    if(c>0) cnt[x]+=cnt[tree[x]]+1;
    tree[x]=s; c++;
}
int pro(int x,int y){
    int i,j,ky=b[(x+y)/2+1].y,r=1,s2=1,dap=0,w1=0,w2=0,w=0;
    for(i=x;i<=y;i++){
        if(a[i].y>ky){
            for(j=s2;j<=w2;j++) go[arr2[j]]=i; s2=w2+1;
            arr1[++w1]=i;
        }
        else arr2[++w2]=i;
    }
    st[0].x=2147483647; top=0;
    for(i=1;i<=w2;i++){
        while(st[top].x<a[arr2[i]].y){
            w++; p[w].x=st[top].pos; p[w].y=a[arr2[i]].x;
            top--;
        }
        top++; st[top].x=a[arr2[i]].y; st[top].pos=arr2[i];
    }
    for(i=1;i<=top;i++){w++; p[w].x=st[i].pos; p[w].y=2147483647;}
    sort(p+1,p+w+1);
    top=0; st[0].x=-1;
    for(j=1;j<=w;j++){
        for(i=r;i<=w1;i++){
            if(a[arr1[i]].x>p[j].y) break;
            while(st[top].x>a[arr1[i]].y){
                tree[st[top].pos]=arr1[i];
                top--;
            }
            top++; st[top].x=a[arr1[i]].y; st[top].pos=arr1[i];
        }
        r=i;
        if(go[p[j].x]>arr1[r-1] || go[p[j].x]==0) continue;
        if(tree[go[p[j].x]]==0){dap++; continue;}
        c=0; dfs(go[p[j].x]); dap+=cnt[go[p[j].x]]+2;
    }
    for(i=1;i<=w1;i++) a2[x+i-1].x=a[arr1[i]].x, a2[x+i-1].y=a[arr1[i]].y;
    for(i=w2;i>=1;i--) a2[y+i-w2].x=a[arr2[i]].x, a2[y+i-w2].y=a[arr2[i]].y;
    for(i=x;i<=y;i++) a[i].x=a2[i].x, a[i].y=a2[i].y;
    for(i=x;i<=y;i++) cnt[i]=0, tree[i]=0, go[i]=0;
    return dap;
}
int divide(int x,int y){
    if(x==y) return 0;
    return pro(x,y)+divide(x,(x+y)/2)+divide((x+y)/2+1,y);
}
int main()
{
    int i,dap;
    scanf("%d",&n);
    for(i=1;i<=n;i++){scanf("%d %d",&a[i].x,&a[i].y); b[i].x=a[i].x; b[i].y=a[i].y;}
    sort(b+1,b+n+1); sort(a+1,a+n+1);
    dap=divide(1,n);
    printf("%d",dap);
}

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