시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 140 18 13 22.807%

문제

연종이는 성공한 벤쳐회사 "봉씨"의 사장이다. 가장 처음에 연종이는 이 회사의 유일한 직원이었다. 하지만, 점점 사업이 성공하면서 연종이는 직원을 뽑게 되었고, 이제 연종이를 제외하고 N명의 직원이 일하는 회사가 되었다.

봉씨에서는 직원의 이름을 부르지 않는 문화가 있다. 모든 직원은 서로를 숫자로 불러야 한다. 숫자는 자신이 들어온 순서대로 1번부터 N번까지 번호매겨진다. 연종이의 번호는 0이다.

새로운 직원이 고용될 때, 그 직원은 기존 직원의 부하로 배정된다. 그리고, 그 직원의 첫 월급은 연종이가 능력을 테스트해 본 후에 정해준다. 

만약, 신입 사원의 월급이 그의 상사보다 많다면, 그 상사의 월급은 신입 사원의 월급 만큼 인상된다. 만약, 월급 인상으로 인해 신입 사원의 상사의 월급이 그의 상사 월급보다 많아진다면, 그 상사의 월급도 신입 사원의 월급 만큼 인상된다. 즉, 상사의 월급과 신입 사원의 월급이 같아지는 것이다. 이 작업은 모든 직원이 자신의 상사보다 월급이 작거나 같을 때 까지 반복된다. 

신입 사원이 채용된 순서와 첫 월급, 그리고 상사의 번호가 주어졌을 때, 새로운 직원이 뽑힐 때 마다, 월급 인상을 받는 직원의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수 N이 주어진다. (1 ≤ N ≤ 300,000)

둘째 줄에는 연종이의 첫 월급이 주어진다.

다음 N개의 줄에는 직원이 고용된 순서대로 I와 B가 주어진다. I는 첫 월급이고, B는 상사의 번호이다.

모든 월급은 1보다 크거나 같고, 109보다 작거나 같다.

출력

각 직원이 고용되었을 때, 월급 인상 받는 직원의 수를 한 줄에 하나씩 N개의 숫자를 출력한다. 

예제 입력 1

7
5000
4500 0
6000 0
4000 1
5500 3
7000 4
6300 2
6300 2

예제 출력 1

0
1
0
2
4
1
0

힌트

W3sicHJvYmxlbV9pZCI6IjMxMDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDRcdWFlMDkgXHVjNzc4XHVjMGMxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1ZjBcdWM4ODVcdWM3NzRcdWIyOTQgXHVjMTMxXHVhY2Y1XHVkNTVjIFx1YmNhNFx1Y2NkMFx1ZDY4Y1x1YzBhYyAmcXVvdDtcdWJkMDlcdWM1MjgmcXVvdDtcdWM3NTggXHVjMGFjXHVjN2E1XHVjNzc0XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzVmMFx1Yzg4NVx1Yzc3NFx1YjI5NCBcdWM3NzQgXHVkNjhjXHVjMGFjXHVjNzU4IFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWM5YzFcdWM2ZDBcdWM3NzRcdWM1YzhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjODEwXHVjODEwIFx1YzBhY1x1YzVjNVx1Yzc3NCBcdWMxMzFcdWFjZjVcdWQ1NThcdWJhNzRcdWMxMWMgXHVjNWYwXHVjODg1XHVjNzc0XHViMjk0IFx1YzljMVx1YzZkMFx1Yzc0NCBcdWJmNTFcdWFjOGMgXHViNDE4XHVjNWM4XHVhY2UwLCBcdWM3NzRcdWM4MWMgXHVjNWYwXHVjODg1XHVjNzc0XHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMCBOXHViYTg1XHVjNzU4IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWM3N2NcdWQ1NThcdWIyOTQgXHVkNjhjXHVjMGFjXHVhYzAwIFx1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDA5XHVjNTI4XHVjNWQwXHVjMTFjXHViMjk0IFx1YzljMVx1YzZkMFx1Yzc1OCBcdWM3NzRcdWI5ODRcdWM3NDQgXHViZDgwXHViOTc0XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWJiMzhcdWQ2NTRcdWFjMDAgXHVjNzg4XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzQwIFx1YzExY1x1Yjg1Y1x1Yjk3YyBcdWMyMmJcdWM3OTBcdWI4NWMgXHViZDg4XHViN2VjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjMjJiXHVjNzkwXHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWI0ZTRcdWM1YjRcdWM2MjggXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWI5ZTRcdWFjYThcdWM5YzRcdWIyZTQuIFx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGM4XHViODVjXHVjNmI0IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWFjZTBcdWM2YTlcdWI0MjAgXHViNTRjLCBcdWFkZjggXHVjOWMxXHVjNmQwXHVjNzQwIFx1YWUzMFx1Yzg3NCBcdWM5YzFcdWM2ZDBcdWM3NTggXHViZDgwXHVkNTU4XHViODVjIFx1YmMzMFx1YzgxNVx1YjQxY1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwLCBcdWFkZjggXHVjOWMxXHVjNmQwXHVjNzU4IFx1Y2NhYiBcdWM2ZDRcdWFlMDlcdWM3NDAgXHVjNWYwXHVjODg1XHVjNzc0XHVhYzAwIFx1YjJhNVx1YjgyNVx1Yzc0NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWQ1NzQgXHViY2Y4IFx1ZDZjNFx1YzVkMCBcdWM4MTVcdWQ1NzRcdWM5MDBcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjljY1x1YzU3ZCwgXHVjMmUwXHVjNzg1IFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWM2ZDRcdWFlMDlcdWM3NzQgXHVhZGY4XHVjNzU4IFx1YzBjMVx1YzBhY1x1YmNmNFx1YjJlNCBcdWI5Y2VcdWIyZTRcdWJhNzQsIFx1YWRmOCBcdWMwYzFcdWMwYWNcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzQwIFx1YzJlMFx1Yzc4NSBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjNmQ0XHVhZTA5IFx1YjljY1x1ZDA3YyBcdWM3NzhcdWMwYzFcdWI0MWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVjNmQ0XHVhZTA5IFx1Yzc3OFx1YzBjMVx1YzczY1x1Yjg1YyBcdWM3NzhcdWQ1NzQgXHVjMmUwXHVjNzg1IFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWMwYzFcdWMwYWNcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzc0IFx1YWRmOFx1Yzc1OCBcdWMwYzFcdWMwYWMgXHVjNmQ0XHVhZTA5XHViY2Y0XHViMmU0IFx1YjljZVx1YzU0NFx1YzljNFx1YjJlNFx1YmE3NCwgXHVhZGY4IFx1YzBjMVx1YzBhY1x1Yzc1OCBcdWM2ZDRcdWFlMDlcdWIzYzQgXHVjMmUwXHVjNzg1IFx1YzBhY1x1YzZkMFx1Yzc1OCBcdWM2ZDRcdWFlMDkgXHViOWNjXHVkMDdjIFx1Yzc3OFx1YzBjMVx1YjQxY1x1YjJlNC4gXHVjOTg5LCBcdWMwYzFcdWMwYWNcdWM3NTggXHVjNmQ0XHVhZTA5XHVhY2ZjIFx1YzJlMFx1Yzc4NSBcdWMwYWNcdWM2ZDBcdWM3NTggXHVjNmQ0XHVhZTA5XHVjNzc0IFx1YWMxOVx1YzU0NFx1YzljMFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuJm5ic3A7XHVjNzc0IFx1Yzc5MVx1YzVjNVx1Yzc0MCBcdWJhYThcdWI0ZTAgXHVjOWMxXHVjNmQwXHVjNzc0IFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWMwYzFcdWMwYWNcdWJjZjRcdWIyZTQgXHVjNmQ0XHVhZTA5XHVjNzc0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDQgXHViNTRjIFx1YWU0Y1x1YzljMCBcdWJjMThcdWJjZjVcdWI0MWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzJlMFx1Yzc4NSBcdWMwYWNcdWM2ZDBcdWM3NzQgXHVjYzQ0XHVjNmE5XHViNDFjIFx1YzIxY1x1YzExY1x1YzY0MCBcdWNjYWIgXHVjNmQ0XHVhZTA5LCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjMGMxXHVjMGFjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjOWMxXHVjNmQwXHVjNzc0IFx1YmY1MVx1ZDc5MCBcdWI1NGMgXHViOWM4XHViMmU0LCBcdWM2ZDRcdWFlMDkgXHVjNzc4XHVjMGMxXHVjNzQ0IFx1YmMxYlx1YjI5NCBcdWM5YzFcdWM2ZDBcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5YzFcdWM2ZDBcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAzMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzVmMFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWNjYWIgXHVjNmQ0XHVhZTA5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMVx1YzZkMFx1Yzc3NCBcdWFjZTBcdWM2YTlcdWI0MWMgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIElcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIElcdWIyOTQgXHVjY2FiIFx1YzZkNFx1YWUwOVx1Yzc3NFx1YWNlMCwgQlx1YjI5NCBcdWMwYzFcdWMwYWNcdWM3NTggXHViYzg4XHVkNjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHVjNmQ0XHVhZTA5XHVjNzQwIDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTA8c3VwPjk8XC9zdXA+XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YzljMVx1YzZkMFx1Yzc3NCBcdWFjZTBcdWM2YTlcdWI0MThcdWM1YzhcdWM3NDQgXHViNTRjLCBcdWM2ZDRcdWFlMDkgXHVjNzc4XHVjMGMxIFx1YmMxYlx1YjI5NCBcdWM5YzFcdWM2ZDBcdWM3NTggXHVjMjE4XHViOTdjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IE5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUE9WSVNJQ0UiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGlzIGEgcHJvdWQgZm91bmRlciBvZiBhIGJpZyBzb2Z0d2FyZSBjb21wYW55LiBJbml0aWFsbHkgaGUgd2FzIHRoZSBvbmx5IHdvcmtlciBpbiB0aGUgY29tcGFueSwgYnV0IGFzIHRoZSBidXNpbmVzcyBncmV3LCBjb21wYW55IGhpcmVkIE4gYWRkaXRpb25hbCB3b3JrZXJzLCBvbmUgYnkgb25lLiBXZSB3aWxsIGRlbm90ZSBNaXJrbyB3aXRoIGludGVnZXIgMCwgYW5kIGVhY2ggb2YgdGhlIHJlbWFpbmluZyB3b3JrZXIgd2l0aCBpbnRlZ2VycyAxIHRvIE4gaW4gb3JkZXIgdGhleSB3ZXJlIGhpcmVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbiB0aGUgZmlyc3QgZGF5IG9mIHdvcmsgZXZlcnkgd29ya2VyIHdhcyBhc3NpZ25lZCBhcyBhIHN1Ym9yZGluYXRlIHRvIGFub3RoZXIgd29ya2VyLiBBbHNvLCBldmVyeSB3b3JrZXIgd2FzIGFzc2lnbmVkIHdpdGggaW5pdGlhbCBzYWxhcnkuIEhvd2V2ZXIsIGlmIHRoZSBzYWxhcnkgb2YgdGhlIG5ldyB3b3JrZXIgd2FzIGdyZWF0ZXIgdGhhbiB0aGUgc2FsYXJ5IG9mIGhpcyBib3NzLCB0aGVuIGhpcyBib3NzIGFsc28gZ290IGEgcmFpc2UgdG8gZXF1YWwgdGhlaXIgc2FsYXJpZXMuIElmIHRoZSBib3NzIG9mIHRoZSBuZXcgd29ya2VyIG5vdyBoYXMgYSBncmVhdGVyIHNhbGFyeSB0aGFuIGhpcyBib3NzLCB0aGUgcHJvY2VkdXJlIGlzIHJlcGVhdGVkIHVudGlsIGV2ZXJ5IHdvcmtlciBoYXMgYSBzYWxhcnkgdGhhdCBpcyBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gdGhlIHNhbGFyeSBvZiBoaXMgYm9zcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBkZXRlcm1pbmUgdGhlIG51bWJlciBvZiB3b3JrZXJzIHRoYXQgZ290IGEgcmFpc2UgZHVyaW5nIHRoZSBwcm9jZXNzIG9mIGhpcmluZyBlYWNoIG5ldyB3b3JrZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBvbmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwMDAwMCksIHRoZSBudW1iZXIgb2Ygd29ya2Vycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIE0sIE1pcmtvJiMzOTtzIGluaXRpYWwgc2FsYXJ5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBOIGxpbmVzIGNvbnRhaW4gdHdvIGludGVnZXJzIGVhY2ggSSBhbmQgQiwgaW5pdGlhbCBzYWxhcnkgb2YgdGhlIG5ldyB3b3JrZXIgYW5kIHRoZSBpbmRleCBvZiBoaXMgYm9zcy4gV29ya2VycyBhcmUgZ2l2ZW4gaW4gdGhlIG9yZGVyIHRoZXkgd2VyZSBoaXJlZCwgaS5lLiBpbiBhc2NlbmRpbmcgb3JkZXIgb2YgdGhlaXIgaW5kaWNlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWxsIHNhbGFyaWVzIGFyZSBpbnRlZ2VycyBiZXR3ZWVuIDEgYW5kIDEwPHN1cD45PFwvc3VwPiBhbmQgYm9zcyBpbmRpY2VzIGFsd2F5cyBkZW5vdGUgYSB3b3JrZXIgdGhhdCB3YXMgYWxyZWFkeSBoaXJlZCBhdCB0aGF0IG1vbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgTiBpbnRlZ2Vycywgb25lIHBlciBsaW5lLCB0aGUgdG90YWwgbnVtYmVyIG9mIHdvcmtlcnMgdGhhdCBnb3QgYSByYWlzZSBkdXJpbmcgdGhlIHByb2Nlc3Mgb2YgaGlyaW5nIGVhY2ggbmV3IHdvcmtlciBpbiBvcmRlciB0aGV5IHdlcmUgaGlyZWQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2010 > Final Exam #2 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: kipa00