[코드포스 Practice6] D. Berstagram

Polycarp recently signed up to a new social network Berstagram. He immediately published nn posts there. He assigned numbers from 11 to nn to all posts and published them one by one. So, just after publishing Polycarp's news feed contained posts from 11 to nn — the highest post had number 11, the next one had number 22, ..., the lowest post had number nn.

After that he wrote down all likes from his friends. Likes were coming consecutively from the 11-st one till the mm-th one. You are given a sequence a1,a2,…,ama1,a2,…,am (1≤aj≤n1≤aj≤n), where ajaj is the post that received the jj-th like.

News feed in Berstagram works in the following manner. Let's assume the jj-th like was given to post ajaj. If this post is not the highest (first) one then it changes its position with the one above. If ajaj is the highest post nothing changes.

For example, if n=3n=3, m=5m=5 and a=[3,2,1,3,3]a=[3,2,1,3,3], then Polycarp's news feed had the following states:

• before the first like: [1,2,3][1,2,3];
• after the first like: [1,3,2][1,3,2];
• after the second like: [1,2,3][1,2,3];
• after the third like: [1,2,3][1,2,3];
• after the fourth like: [1,3,2][1,3,2];
• after the fifth like: [3,1,2][3,1,2].

Polycarp wants to know the highest (minimum) and the lowest (maximum) positions for each post. Polycarp considers all moments of time, including the moment "before all likes".

 

Input

The first line contains two integer numbers nn and mm (1≤n≤1051≤n≤105, 1≤m≤4⋅1051≤m≤4⋅105) — number of posts and number of likes.

The second line contains integers a1,a2,…,ama1,a2,…,am (1≤aj≤n1≤aj≤n), where ajaj is the post that received the jj-th like.

 

Output

Print nn pairs of integer numbers. The ii-th line should contain the highest (minimum) and the lowest (maximum) positions of the ii-th post. You should take into account positions at all moments of time: before all likes, after each like and after all likes. Positions are numbered from 11 (highest) to nn (lowest).

---

아 쉽네.. 하다가 멈짓한 문제

 

처음에 n칸짜리 위치를 저장하는 배열 만들어서 3 들어오면 a[3]-- 이런 식으로 짜려 했는데 생각해보니깐 이전 위치의 값도 변경해줘야 했다ㅋㅋㅋ 처음에 풀 때 여기서 막혔던게 기억난다. 

 

그래서 3의 위치는 알 수 있으니 그 이전 위치의 값을 찾아서 풀려고 했다. 이제 탐색이 문젠데 그냥 쭉 찾으면 입력이 십만이라 십만*십만 = 터진다.. 내가 아는 빠른 탐색은 이분탐색이지만 그건 정렬된 상태에서 써야 하는거라 못 쓴다. 

 

다음으로 뭔가 느낌이 투포인터 쓰면 될 것 같았다. (근거없음) 값 두개만 변경되고 막 k-도미넌트 문제도 떠오르고.. 하지만 아니어서 바로 접었다ㅋㅋㅋ

 

 

그 다음 생각난게 이전 위치랑 현 위치 둘 다 저장하면 되지 않을까?? 했는데 이것도 허점이 있어서 버리고 결국 이전위치, 현위치, 다음위치 세가지를 저장하는 벡터를 만들었다. 이제 값 들어오면 영차영차 바꿔주면 된다. (복잡해!)

 

바꿔주는 건 이렇게 생김.. 여기서 최대, 최소 비교하는 부분이랑 현위치가 1이면 안 바꿔주는 것만 추가하면 된다. 

그렇게 어렵지는 않은데.. 음.. 저거 구현하는데 시간이 많이 걸렸다. 

 

결과는..

결과.. 

맞았다! 코포 그냥 마 맞다고 하지 예제 엄청 많이 돌리네

---

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

    //왜 n+5일까??
	vector<ii> pos(n + 5);  //최대위치와 최소위치 
	vector<int> now(n + 5); //현위치
	vector<int> arr(n + 5); //이 위치에 있는 값

    //초기화
	for (int i = 1; i <= n; i++)
		pos[i].xx = pos[i].yy = now[i] = arr[i] = i;

	for (int i = 0; i < m; i++)
	{
		int x;
		scanf("%d", &x);

		if (now[x] == 1)
			continue;
        
        //x의 현재위치 nx
		int nx = now[x];
		swap(arr[nx], arr[nx - 1]);     //nx에 있는 값과 nx의 앞에 있는 값 바꿈
		now[arr[nx]] = nx;      //arr[nx] : nx위치에 있는 값 now[arr[nx]] : 그 값의 현위치를 nx로 수정함 
		now[arr[nx - 1]] = nx - 1;

		pos[arr[nx]].xx = min(pos[arr[nx]].xx, nx); //최대최소 변경
		pos[arr[nx]].yy = max(pos[arr[nx]].yy, nx); //
		
		pos[arr[nx - 1]].xx = min(pos[arr[nx - 1]].xx, nx - 1); //nx - 1 최대최소변경
		pos[arr[nx - 1]].yy = max(pos[arr[nx - 1]].yy, nx - 1);
	}

	for (int i = 1; i <= n; i++)
		printf("%d %d\n", pos[i].xx, pos[i].yy);

	return 0;
}

이건 북님 코드

비슷한 것 같으면서 안 비슷한 거 같기도 하고?

 

난 구조체 만들어서 다 때려넣었는데 저렇게 나눠서 정리하는 것도 괜찮아 보인다. 아 그리고 +5 한 건 그냥 낙낙히 잡은거라 하심