백준 2568번 전깃줄 소스코드

https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

 

[ 백준 2568번 전깃줄 -2 소스코드 ]

[ 한국정보올림피아드 시도 지역본선 - 지역본선 2007 - 중등부 3번 - 전깃줄 소스코드 ]

#include <stdio.h>
#include <algorithm>
struct wire
{
	int a, b;
}aa[1200000];

int sortf(wire x, wire y)
{
	if(x.a<y.a) return 1;
	else return 0;
}

int a[1200000], b[1200000], c[1200000], d[1200000];


int main()
{
	int i;
	int l, r, max=0, t, n, x, dab=0, s, k;
	
	scanf("%d", &n); 
	t=524288;
	
	for(i=t;i<t+n;i++)
		scanf("%d %d", &aa[i].a, &aa[i].b);
		
	std::sort(aa+t, aa+t+n, sortf);
	
	for(i=t;i<t+n;i++)
		printf("%d %d\n", aa[i].a, aa[i].b);
		
	for(i=t;i<t+n;i++)
	{
		x=aa[i].b; 
		l=t; 
		r=t+x-1; 
		max=1; 
		s=-1;
		while(1)
		{
			if(l==r)
			{
				if(a[l]>=max)
				{ 
					max=a[l]; 
					s=b[l]; 
				}
				break;
			}
			if(l&1)
			{
				if(a[l]>=max)
				{ 
					max=a[l]; 
					s=b[l]; 
				}
				l++;
			}
			if(!(r&1))
			{
				if(a[r]>=max)
				{ 
					max=a[r]; 
					s=b[r]; 
				}
				r--;
			}
			if(l>r)
			{
				if(a[l]>=max)
				{ 
					max=a[l]; 
					s=b[l]; 
				}
				if(a[r]>=max)
				{ 
					max=a[r]; 
					s=b[r]; 
				}
				break;
			}
			l>>=1;   // l = l / 2
			r>>=1;   // r = r / 2
		}
		l=t+x-1; 
		c[i]=s;
		
		while(1)
		{
			if(max+1>=a[l])
			{ 
				a[l]=max+1; 
				b[l]=i; 
			}
			else break;
			
			l>>=1;
			if(l==0) break;
		}

		if(a[t+x-1]>=dab)
		{ 
			dab=a[t+x-1]; 
			k=i; 
		}
	}

	while(1)
	{
		if(k<1) break;
		d[k]=1; 
		k=c[k];
	}

	printf("%d\n", n-dab+1);
	
	for(i=t;i<t+n;i++)
	{
		if(d[i]==0) 
			printf("%d\n", aa[i].a);
	}
}