Submission #12766

#	Time	Username	Problem	Language	Result	Execution time	Memory
12766		dohyun0324	전선 연결하기 (GA9_wire)	C++98	100 / 100	916 ms	36248 KiB

wire

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int max(int x,int y){
    if(x>y) return x;
    return y;
}
int min(int x,int y){
    if(x>y) return y;
    return x;
}
int n;
int s1,e1,p,t=1,a[600010],ch[600010],top,q[300010],s[300010],e[300010],dap[300010],f,r,treeb[2200010],treef[2200010],tree[2200010];
void update(int x,int gap)
{
    int s=x+t-1;
    tree[s]=gap;
    s/=2;
    while(s>0){
        tree[s]=max(tree[s*2],tree[s*2+1]);
        s/=2;
    }
}
void updatef(int x,int gap)
{
    int s=x+t-1;
    treef[s]=gap;
    s/=2;
    while(s>0){
        treef[s]=min(treef[s*2],treef[s*2+1]);
        s/=2;
    }
}
void updateb(int x,int gap)
{
    int s=x+t-1;
    treeb[s]=gap;
    s/=2;
    while(s>0){
        treeb[s]=max(treeb[s*2],treeb[s*2+1]);
        s/=2;
    }
}
int queryf(int x,int y,int k)
{
    if(s1<=x && y<=e1) return treef[k];
    if(s1>y || e1<x) return 2147483647;
    return min(queryf(x,(x+y)/2,k*2),queryf((x+y)/2+1,y,k*2+1));
}
int queryb(int x,int y,int k)
{
    if(s1<=x && y<=e1) return treeb[k];
    if(s1>y || e1<x) return 0;
    return max(queryb(x,(x+y)/2,k*2),queryb((x+y)/2+1,y,k*2+1));
}
int query(int x,int y,int k)
{
    if(s1<=x && y<=e1) return tree[k];
    if(s1>y || e1<x) return 0;
    return max(query(x,(x+y)/2,k*2),query((x+y)/2+1,y,k*2+1));
}
void check()
{
    int i;
    //1
    for(i=1;i<=n;i++){
        if(dap[i]==1) update(s[i],e[i]);
    }
    for(i=1;i<=n;i++){
        if(dap[i]==1)
        {
            s1=s[i]+1; e1=e[i]-1;
            if(query(1,t,1)>e[i]){printf("IMPOSSIBLE"); exit(0);}
        }
    }
    memset(tree,0,sizeof tree);
    //0
    for(i=1;i<=n;i++){
        if(dap[i]==0) update(s[i],e[i]);
    }
    for(i=1;i<=n;i++){
        if(dap[i]==0)
        {
            s1=s[i]+1; e1=e[i]-1;
            if(query(1,t,1)>e[i]){printf("IMPOSSIBLE"); exit(0);}
        }
    }
}
int main()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n*2;i++)
    {
        scanf("%d",&a[i]);
        if(s[a[i]]==0) s[a[i]]=i;
        else e[a[i]]=i;
    }
    for(i=1;;i++){if(t>=n*2) break; t*=2;}
    for(i=1;i<=t*2;i++) treef[i]=2147483647;
    for(i=1;i<=n;i++)
    {
        updatef(e[i],s[i]);
        updateb(s[i],e[i]);
    }
    for(i=1;i<=n;i++)
    {
        if(ch[i]==0)
        {
            dap[i]=1;
            q[++r]=i;
            updatef(e[i],2147483647);
            updateb(s[i],0);
            while(f!=r)
            {
                f++;
                for(;;)
                {
                    s1=s[q[f]]+1; e1=e[q[f]]-1;
                    p=queryf(1,t,1);
                    if(p>=s[q[f]] || s1>e1) break;
                    updatef(e[a[p]],2147483647);
                    updateb(s[a[p]],0);
                    dap[a[p]]=(dap[q[f]]+1)%2;
                    ch[a[p]]=1;
                    q[++r]=a[p];
                }
                for(;;)
                {
                    s1=s[q[f]]+1; e1=e[q[f]]-1;
                    p=queryb(1,t,1);
                    if(p<=e[q[f]] || s1>e1) break;
                    updateb(s[a[p]],0);
                    updatef(e[a[p]],2147483647);
                    dap[a[p]]=(dap[q[f]]+1)%2;
                    ch[a[p]]=1;
                    q[++r]=a[p];
                }
            }
        }
    }
    check();
    for(i=1;i<=n*2;i++)
    {
        if(dap[a[i]]==0) printf("v");
        else printf("^");
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 37 / 37
• Subtask 4: 39 / 39