Submission #12828

#	Time	Username	Problem	Language	Result	Execution time	Memory
12828		ainta	전선 연결하기 (GA9_wire)	C++98	100 / 100	596 ms	39632 KiB

wire

#include<stdio.h>
#include<algorithm>
using namespace std;
#define SZ 1048576
int n, chk[301000], num[601000];
int st[601000];
struct IdxTree{
	int r, l;
}IT[SZ + SZ + 1];
struct point{
	int b, e;
}w[301000];
void UDT(int x){
	while (x != 1){
		x >>= 1;
		if (w[IT[x * 2].l].b <= w[IT[x * 2 + 1].l].b)IT[x].l = IT[x * 2].l;
		else IT[x].l = IT[x * 2 + 1].l;
		if (w[IT[x * 2].r].e >= w[IT[x * 2 + 1].r].e)IT[x].r = IT[x * 2].r;
		else IT[x].r = IT[x * 2 + 1].r;
	}
}
void Ins(int x, int a){
	x += SZ;
	IT[x].l = IT[x].r = a;
	UDT(x);
}
void Del(int x){
	x += SZ;
	IT[x].l = IT[x].r = 0;
	UDT(x);
}
int Left(int b, int e){
	int r = 0;
	b += SZ, e += SZ;
	while (b <= e){
		if (w[r].b > w[IT[b].l].b)r = IT[b].l;
		if (w[r].b > w[IT[e].l].b)r = IT[e].l;
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	return r;
}
int Right(int b, int e){
	int r = 0;
	b += SZ, e += SZ;
	while (b <= e){
		if (w[r].e < w[IT[b].r].e)r = IT[b].r;
		if (w[r].e < w[IT[e].r].e)r = IT[e].r;
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	return r;
}
bool Check(int ck){
	int i, top = 0;
	for (i = 1; i <= 2 * n; i++){
		if (chk[num[i]] != ck)continue;
		if (st[top] == num[i])top--;
		else st[++top] = num[i];
	}
	if (top)return false;
	return true;
}
void DFS(int a, int b){
	chk[a] = b;
	int i, l, r;
	Del(w[a].b);
	Del(w[a].e);
	while (1){
		l = Left(w[a].b, w[a].e);
		if (w[l].b < w[a].b)DFS(l, 3 - b);
		else break;
	}
	while (1){
		r = Right(w[a].b, w[a].e);
		if (w[r].e > w[a].e)DFS(r, 3 - b);
		else break;
	}
}
int main(){
	int i, a, t;
	scanf("%d", &n);
	w[0].b = 2 * n + 1, w[1].e = 0;
	for (i = 1; i <= 2 * n; i++){
		scanf("%d", &a);
		num[i] = a;
		if (!w[a].b)w[a].b = i;
		else w[a].e = i;
	}
	for (i = 1; i <= n; i++){
		Ins(w[i].b, i);
		Ins(w[i].e, i);
	}
	for (i = 1; i <= n; i++){
		if (!chk[i]){
			DFS(i, 1);
		}
	}
	if (Check(1) && Check(2)){
		for (i = 1; i <= 2 * n; i++){
			if (chk[num[i]] == 1)printf("^");
			else printf("v");
		}
	}
	else printf("IMPOSSIBLE\n");
	return 0;
}

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