Submission #128101

#	Time	Username	Problem	Language	Result	Execution time	Memory
128101		yuree5	곡선 자르기 (KOI17_cut)	C++14	35 / 100	1085 ms	17556 KiB

cut

#include <cstdio>

int n,cnt;
int vt[1000010],vtt[1000010];
struct xy{
    int x,y;
};
xy B[1000010];
struct se{
    int s,e;
};
int c;
se C[1000010],t[1000010];
void mers(int s,int m,int e){
    int i,p1=s,p2=m+1;
    for(i=s;i<=e;i++){
        if(p1>m||(p2<=e&&C[p1].s>C[p2].s))t[i]=C[p2++];
        else if((p2<=e&&C[p1].s==C[p2].s)){
            if(C[p1].e<C[p2].s)t[i]=C[p2++];
        }
        else t[i]=C[p1++];
    }
    for(i=s;i<=e;i++){
        C[i]=t[i];
    }
}
void msort(int s,int e){
    if(s>=e)return;
    int m=(s+e)/2;
    msort(s,m);
    msort(m+1,e);
    mers(s,m,e);
}
bool re(int a){
    int j=a+1;
    vt[a]=1;
   // printf("%d: (%d %d)\n",a,C[a].s,C[a].e);
    bool chk=true;
    while(C[a].e>C[j].e&&C[a].s<C[j].s&&j<c){
     //   printf("%d %d %d %d\n",C[a].s,C[j].s,C[j].e,C[a].e);
        if(vt[j]==0){vt[j]=1;vtt[j]=1;re(j);}
        j++;
        chk=false;
    }   // printf("    (%d  %d) %d\n",a,chk,i);
    if(chk==1){cnt++; return 0;}
    else return 1;
}
int main(){
   // freopen("input.txt","r",stdin);
    scanf("%d",&n);
    int i,mx=0,my=1000000010,mxi=0;
    for(i=0;i<n;i++){
        scanf("%d %d",&B[i].x,&B[i].y);
        if(B[i].x>mx){
            if(B[i].y<=my){
                mx=B[i].x;
                my=B[i].y;
                mxi=i;
            }
        }else if(B[i].x==mx&&B[i].y<my){
            mx=B[i].x;my=B[i].y;
            mxi=i;
        }
    }
    int s,e,v=0;
    for(i=mxi;i<n;i++){
        int val=i+1;
        if(val==n)val=0;
        if(B[i].y<0&&B[val].y>0){v=1;s=B[i].x;}
        if(v==1&&B[i].y>0&&B[val].y<0){
            v=0;
            C[c].s=s;
            C[c++].e=B[i].x;
        }
    }
    for(i=0;i<mxi;i++){
        if(B[i].y<0&&B[i+1].y>0){v=1;s=B[i].x;}
        if(v==1&&B[i].y>0&&B[i+1].y<0){
            v=0;
            C[c].s=s;
            C[c++].e=B[i].x;
        }
    }
    for(i=0;i<c;i++){
        if(C[i].e<C[i].s){
            int t=C[i].e;
            C[i].e=C[i].s;
            C[i].s=t;
        }
    }
    msort(0,c-1);
    int j,ccnt=0;
    //printf("\n\n");
    for(i=0;i<c;i++){
        if(vt[i]==0){re(i);vt[i]=1;}
    }
    for(i=0;i<c;i++){
        if(vtt[i]==0)ccnt++;
    }
    printf("%d %d",ccnt,cnt);
}

Compilation message (stderr)

cut.cpp: In function 'int main()':
cut.cpp:65:11: warning: unused variable 'e' [-Wunused-variable]
     int s,e,v=0;
           ^
cut.cpp:92:9: warning: unused variable 'j' [-Wunused-variable]
     int j,ccnt=0;
         ^
cut.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
cut.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&B[i].x,&B[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 0 / 65