Submission #12752

#	Time	Username	Problem	Language	Result	Execution time	Memory
12752		dohyun0324	전선 연결하기 (GA9_wire)	C++98	61 / 100	356 ms	17496 KiB

wire

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n;
int p,t=1,a[600010],ch[300010],top,q[600010],s[300010],e[300010],dap[300010],f,r,treeb[600010],treef[600010],tree[600010];
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,int s,int e)
{
    if(s>e) return 2147483647;
    if(s<=x && y<=e) return treef[k];
    if(s>y || e<x) return 2147483647;
    return min(queryf(x,(x+y)/2,k*2,s,e),queryf((x+y)/2+1,y,k*2+1,s,e));
}
int queryb(int x,int y,int k,int s,int e)
{
    if(s>e) return 0;
    if(s<=x && y<=e) return treeb[k];
    if(s>y || e<x) return 0;
    return max(queryb(x,(x+y)/2,k*2,s,e),queryb((x+y)/2+1,y,k*2+1,s,e));
}
int query(int x,int y,int k,int s,int e)
{
    if(s>e) return 0;
    if(s<=x && y<=e) return tree[k];
    if(s>y || e<x) return 0;
    return max(query(x,(x+y)/2,k*2,s,e),query((x+y)/2+1,y,k*2+1,s,e));
}
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 && query(1,t,1,s[i]+1,e[i]-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 && query(1,t,1,s[i]+1,e[i]-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)
        {
            ch[i]=1;
            dap[i]=1;
            q[++r]=i;
            updatef(e[i],2147483647);
            updateb(s[i],0);
            while(f!=r)
            {
                f++;
                while(queryf(1,t,1,s[q[f]]+1,e[q[f]]-1)<s[q[f]])
                {
                    p=queryf(1,t,1,s[q[f]]+1,e[q[f]]-1);
                    updatef(e[a[p]],2147483647);
                    dap[a[p]]=(dap[q[f]]+1)%2;
                    ch[a[p]]=1;
                    q[++r]=a[p];
                }
                while(queryb(1,t,1,s[q[f]]+1,e[q[f]]-1)>e[q[f]])
                {
                    p=queryb(1,t,1,s[q[f]]+1,e[q[f]]-1);
                    updateb(s[a[p]],0);
                    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: 0 / 39