#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int n;
int p,t=1,a[1200010],ch[1200010],top,q[2000010],s[1200010],e[1200010],dap[1200010],f,r,treeb[3000010],treef[3000010],tree[3000010];
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Memory limit exceeded |
0 ms |
65536 KB |
Memory limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
