시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 142 44 37 30.833%

문제

디지털 음악에서 소리는 대기압의 변화를 나타내는 숫자로 표현한다. 대기압의 변화는 일정한 시간 구간을 정해놓고, 연속되는 구간동안 얼마나 빠르게 변했는지를 측정한다. 이렇게 측정한 값을 샘플이라고 한다.

음성 처리에서 가장 중요한 단계는 녹음된 소리를 사일런스 기준으로 사일런스가 아닌 구간으로 나누는 작업이다. 너무 많은 조각이 나는 것을 방지 하기 위해서 사일런스는 최저값과 최고값의 차이가 c를 넘지않는 샘플 m개의 연속이라고 정의한다.

샘플 n개 이루어진 레코딩과 m과 c가 주어졌을 때, 사일런스를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 샘플의 수 n (1 <= n <= 1,000,000), m (1 <= m <= 10,000), c (0 <= c <= 10,000)가 주어진다.

둘째 줄에는 각 샘플의 값 ai가 주어진다. (0 <= ai <= 1,000,000 for 1 <= i <= n)

출력

max(a[i . . . i+m−1])−min(a[i . . . i+m−1]) <= c를 만족하는 모든 i를 오름차순으로 한 줄에 하나씩 출력한다.

만약, 주어진 입력에 사일런스가 없다면, NONE을 출력한다.

예제 입력 1

7 2 0
0 1 1 2 3 2 2

예제 출력 1

2
6

힌트

W3sicHJvYmxlbV9pZCI6IjI0MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJUaGUgU291bmQgb2YgU2lsZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+XHViNTE0XHVjOWMwXHVkMTM4IFx1Yzc0Y1x1YzU0NVx1YzVkMFx1YzExYyBcdWMxOGNcdWI5YWNcdWIyOTQgXHViMzAwXHVhZTMwXHVjNTU1XHVjNzU4IFx1YmNjMFx1ZDY1NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjJiXHVjNzkwXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1Y1x1YjJlNC4gXHViMzAwXHVhZTMwXHVjNTU1XHVjNzU4IFx1YmNjMFx1ZDY1NFx1YjI5NCBcdWM3N2NcdWM4MTVcdWQ1NWMgXHVjMmRjXHVhYzA0IFx1YWQ2Y1x1YWMwNFx1Yzc0NCBcdWM4MTVcdWQ1NzRcdWIxOTNcdWFjZTAsIFx1YzVmMFx1YzE4ZFx1YjQxOFx1YjI5NCBcdWFkNmNcdWFjMDRcdWIzZDlcdWM1NDggXHVjNWJjXHViOWM4XHViMDk4IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWJjYzBcdWQ1ODhcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZTIxXHVjODE1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjZTIxXHVjODE1XHVkNTVjIFx1YWMxMlx1Yzc0NCBcdWMwZDhcdWQ1MGNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NGNcdWMxMzEgXHVjYzk4XHViOWFjXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM5MTFcdWM2OTRcdWQ1NWMgXHViMmU4XHVhY2M0XHViMjk0IFx1YjE3OVx1Yzc0Y1x1YjQxYyBcdWMxOGNcdWI5YWNcdWI5N2MgXHVjMGFjXHVjNzdjXHViN2YwXHVjMmE0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWMwYWNcdWM3N2NcdWI3ZjBcdWMyYTRcdWFjMDAgXHVjNTQ0XHViMmNjIFx1YWQ2Y1x1YWMwNFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWIyOTQgXHVjNzkxXHVjNWM1XHVjNzc0XHViMmU0LiBcdWIxMDhcdWJiMzQgXHViOWNlXHVjNzQwIFx1Yzg3MFx1YWMwMVx1Yzc3NCBcdWIwOThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YmMyOVx1YzljMCBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzBhY1x1Yzc3Y1x1YjdmMFx1YzJhNFx1YjI5NCBcdWNkNWNcdWM4MDBcdWFjMTJcdWFjZmMgXHVjZDVjXHVhY2UwXHVhYzEyXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCBjXHViOTdjIFx1YjExOFx1YzljMFx1YzU0YVx1YjI5NCBcdWMwZDhcdWQ1MGMgbVx1YWMxY1x1Yzc1OCBcdWM1ZjBcdWMxOGRcdWM3NzRcdWI3N2NcdWFjZTAgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwZDhcdWQ1MGMgblx1YWMxYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViODA4XHVjZjU0XHViNTI5XHVhY2ZjIG1cdWFjZmMgY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYWNcdWM3N2NcdWI3ZjBcdWMyYTRcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBkOFx1ZDUwY1x1Yzc1OCBcdWMyMTggbiZuYnNwOygxICZsdDs9XHUwMDE0IG4gJmx0Oz1cdTAwMTRcdTAwMTQgMSwwMDAsMDAwKSwgbSAoMSBcdTAwMTQmbHQ7PVx1MDAxNCBtIFx1MDAxNCZsdDs9XHUwMDE0IDEwLDAwMCksIGMgKDAgXHUwMDE0Jmx0Oz1cdTAwMTQgYyAmbHQ7PVx1MDAxNFx1MDAxNCAxMCwwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjMGQ4XHVkNTBjXHVjNzU4IFx1YWMxMiBhPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDAgJmx0Oz1cdTAwMTRcdTAwMTQgYTxzdWI+aTxcL3N1Yj4gXHUwMDE0Jmx0Oz1cdTAwMTQgMSwwMDAsMDAwIGZvciAxICZsdDs9XHUwMDE0XHUwMDE0IGkgJmx0Oz1cdTAwMTRcdTAwMTQgbik8XC9wPlxyXG5cclxuXHJcbiIsIm91dHB1dCI6IjxwPm1heChhW2kgLiAuIC4gaSttJm1pbnVzOzFdKSZtaW51czttaW4oYVtpIC4gLiAuIGkrbSZtaW51czsxXSkgXHUwMDE0Jmx0Oz0gY1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViYWE4XHViNGUwIGlcdWI5N2MgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjNzg1XHViODI1XHVjNWQwIFx1YzBhY1x1Yzc3Y1x1YjdmMFx1YzJhNFx1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQsIE5PTkVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8aWZyYW1lIHdpZHRoPVwiOTYwXCIgaGVpZ2h0PVwiNzIwXCIgc3JjPVwiXC9cL3d3dy55b3V0dWJlLmNvbVwvZW1iZWRcL2RUQ053Z3pNMnJRXCIgZnJhbWVib3JkZXI9XCIwXCIgYWxsb3dmdWxsc2NyZWVuPjxcL2lmcmFtZT4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaGUgU291bmQgb2YgU2lsZW5jZSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gZGlnaXRhbCByZWNvcmRpbmcsIHNvdW5kIGlzIGRlc2NyaWJlZCBieSBhIHNlcXVlbmNlIG9mIG51bWJlcnMgcmVwcmVzZW50aW5nIHRoZSBhaXIgcHJlc3N1cmUsIG1lYXN1cmVkIGF0IGEgcmFwaWQgcmF0ZSB3aXRoIGEgZml4ZWQgdGltZSBpbnRlcnZhbCBiZXR3ZWVuIHN1Y2Nlc3NpdmUgbWVhc3VyZW1lbnRzLiBFYWNoIHZhbHVlIGluIHRoZSBzZXF1ZW5jZSBpcyBjYWxsZWQgYSBzYW1wbGUuPFwvcD5cclxuXHJcbjxwPkFuIGltcG9ydGFudCBzdGVwIGluIG1hbnkgdm9pY2UtcHJvY2Vzc2luZyB0YXNrcyBpcyBicmVha2luZyB0aGUgcmVjb3JkZWQgc291bmQgaW50byBjaHVua3Mgb2Ygbm9uLXNpbGVuY2Ugc2VwYXJhdGVkIGJ5IHNpbGVuY2UuIFRvIGF2b2lkIGFjY2lkZW50YWxseSBicmVha2luZyB0aGUgcmVjb3JkaW5nIGludG8gdG9vIGZldyBvciB0b28gbWFueSBwaWVjZXMsIHRoZSBzaWxlbmNlIGlzIG9mdGVuIGRlZmluZWQgYXMgYSBzZXF1ZW5jZSBvZiBtIHNhbXBsZXMgd2hlcmUgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGUgbG93ZXN0IGFuZCB0aGUgaGlnaGVzdCB2YWx1ZSBkb2VzIG5vdCBleGNlZWQgYSBjZXJ0YWluIHRyZXNob2xkIGMuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBkZXRlY3Qgc2lsZW5jZSBpbiBhIGdpdmVuIHJlY29yZGluZyBvZiBuIHNhbXBsZXMgYWNjb3JkaW5nIHRvIHRoZSBnaXZlbiBwYXJhbWV0ZXIgdmFsdWVzIG0gYW5kIGMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdGhyZWUgaW50ZWdlcnM6IG4gKDEgJmx0Oz1cdTAwMTQgbiAmbHQ7PVx1MDAxNFx1MDAxNCAxLDAwMCwwMDApLCB0aGUgbnVtYmVyIG9mIHNhbXBsZXMgaW4gdGhlIHJlY29yZGluZzsgbSAoMSBcdTAwMTQmbHQ7PVx1MDAxNCBtIFx1MDAxNCZsdDs9XHUwMDE0IDEwLDAwMCksIHRoZSByZXF1aXJlZCBsZW5ndGggb2YgdGhlIHNpbGVuY2U7IGFuZCBjICgwIFx1MDAxNCZsdDs9XHUwMDE0IGMgJmx0Oz1cdTAwMTRcdTAwMTQgMTAsMDAwKSwgdGhlIG1heGltYWwgbm9pc2UgbGV2ZWwgYWxsb3dlZCB3aXRoaW4gc2lsZW5jZS48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBuIGludGVnZXJzIGFpICgwICZsdDs9XHUwMDE0XHUwMDE0IGFpIFx1MDAxNCZsdDs9XHUwMDE0IDEsMDAwLDAwMCBmb3IgMSAmbHQ7PVx1MDAxNFx1MDAxNCBpICZsdDs9XHUwMDE0XHUwMDE0IG4pLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIHNwYWNlczogdGhlIHNhbXBsZXMgaW4gdGhlIHJlY29yZGluZy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBsaXN0IGFsbCB2YWx1ZXMgb2YgaSBzdWNoIHRoYXQgbWF4KGFbaSAuIC4gLiBpK20mbWludXM7MV0pJm1pbnVzO21pbihhW2kgLiAuIC4gaSttJm1pbnVzOzFdKSBcdTAwMTQmbHQ7PSBjLiBUaGUgdmFsdWVzIHNob3VsZCBiZSBsaXN0ZWQgaW4gaW5jcmVhc2luZyBvcmRlciwgZWFjaCBvbiBhIHNlcGFyYXRlIGxpbmUuPFwvcD5cclxuXHJcbjxwPjxiciBcLz5cclxuSWYgdGhlcmUgaXMgbm8gc2lsZW5jZSBpbiB0aGUgaW5wdXQsIHdyaXRlIE5PTkUgb24gdGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 3번