10-11 класс

(Темірлан vs Рамазан) Тақтада $N$ бүтін сан жазылған. Темірлан және Рамазан келесі ойынды ойнап жатыр:

• Олар кезектесіп жүреді, бірінші болып Темірлан жүреді.
  
• Әр жүрісте ойыншы тақтадан кез-келген бастапқы сандарды немесе соңғы сандарды өшіріп тастайды, және кем дегенде бір санды өшіру керек. Бірақ барлық санды өшіріп тастауға болмайды.
  
• Тақтада соңғы сан қалғанда ойын аяқталады. Темірлан сол санның барынша кішкентай болғаның қалайды, ал Рамазан барынша үлкен болғаның қалайды.
  

Темірлан сыртқа шығып кеткенде, Рамазан тақтадғы $K$ санды өшіріп тастағысы келеді. Ол кез келген сандарды өшіріп тастай алады. Темірлан қайтып келгенде, олар ойынды ойнап бастайды, бірақ тақтада $N-K$ сан жазылып тұрады.
Әрбір $Q$ сан $K_1,K_2, ..., K_Q$ үшін, Рамазан ойында қалған соңғы санның мәнің білгісі келеді, егер ол ойынның басында $K_i$ санды өшіріп тастаса, және екі ойыншыда өзіне қолайлы ойнаса?

Кіріс деректер форматы:

Бірінші жолда бір бүтін сан $N$ берілген.
Екінші жолда $N$ бүтін сан берілген $A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- тақтада жазылған сандар.
Үшінші жолда бір бүтін сан $Q$ берілген.
Төртінші жолда $Q$ бүтін сан берілген $K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$.

Шығыс деректер форматы:

Пробел арқылы $Q$ сан шығарыңыз, $i$-ші сан, ол соңғы қалған санның мәні, егер Рамазан алдын ала $K_i$ санды өшіріп тастаса.

Мысалдар:

1.Мысал:

4
1 4 2 3
4
0 1 2 3

Жауап:

1 3 3 4

2.Мысал:

3
5 5 5
3
0 1 2

Жауап:

5 5 5

3.Мысал:

6
2 7 5 4 8 10
3
3 5 2

Жауап:

7 10 7

Түсініктеме:

Бірінші тестте $K=3$ болғанда, Рамазанға бірінші,екінші және төртінші санды өшірген тиімді.

Бағалау:

Есеп 50 тесттен тұрады, әр тест 2 ұпаіға бағаланады.
Тесттердегі шектеулер:

• 3 тест: Алғашқы үш тест мысалда берілген тесттер
  
• 5 тест: $1 \le N \le 3, Q = 1, K_1 = 0$
  
• 10 тестте: $1 \le N \le 100, Q = 1, K_1 = 0$
  
• 12 тестте: $1 \le N \le 10^5, 1\le Q \le 2, 0 \le K_i \le 1$
  
• 10 тестте: $1 \le N \le 10^5, 1 \le Q \le 10^5,0 \le K_i \le N - 1$
  
• 10 тестте: $1 \le N \le 10^6, 1 \le Q \le 10^6, 0 \le K_i \le N - 1$
  

( Temirlan Satylkhanov )

Комментарий/решение

Когда именно выдается вердикт Check Failed?

кодты корсету/жасыру

#include <bits/stdc++.h>
#define f first
#define se second
using namespace std;
const int N = (int)(1e6 + 123);
pair <int , int> a[N];
int k[N] , ans[N] , b[N];
set <int> st;
int main() {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i].f;
        b[i] = a[i].f;
        a[i].se = i;
    }
    sort(a + 1 , a + 1 + n);
    for (int i=1; i<=n; i++) st.insert(i);
    for (int i=0; i<n; i++) {
        ans[i] = min(b[*st.begin()] , b[*st.rbegin()]);
        st.erase(a[i+1].se);
    }
    int q;
    cin >> q;
    for (int i=1; i<=q; i++) cin >> k[i];
    for (int i=1; i<=q; i++) cout <<ans[k[i]]<<" ";
    return 0;
}

Работает на претестах но говорит "ошибка проверки" что это значит?

исправлена ошибка в проверяющей системе. попробуйте переотправить.

Заработала спасибо!

можно разбор

А как проверить решение? В этой задаче нельзя же проверить.

админ можно разбор этой задачи

Можно доказать, если есть последовательность $a_1, a_2, ..., a_n$ то в конце останется число $min(a_1,a_n)$

Для того что бы получить число С мы должны на префиксе жадно удалить все числа меньше С и на суффиксе тоже. Если удалили $len$ чисел то $ans[len] >= C$.

кодты корсету/жасыру

const int N = int(1e6) + 10, mod = int(1e9)  + 7; 

int n,q, a[N];

int mx, pref[N], suf[N], ans[N];

int main () {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	mx = 0;
	for(int i = 1; i <= n; i++){
		for(int j = mx + 1; j <= a[i]; j++){
		    pref[j] = i;
		}
		mx = max(mx, a[i]);
	}
	mx = 0;
	for(int i = n; i > 0; i--){
		for(int j = mx + 1; j <= a[i]; j++){
			suf[j] = i;
		}
		mx = max(mx, a[i]);
	}

	for(int i = 1, len; i <= mx; i++){
		len = pref[i] - 1  + n - suf[i];
		ans[len] = i;
	}
	for(int i = 1; i <= n; i++){
		ans[i] = max(ans[i - 1], ans[i]);
	}
	scanf("%d", &q);
	for(int i = 1,k; i <= q; i++){
		scanf("%d", &k);
		printf("%d", ans[k]);
		if(i < q) printf(" ");
	}


return 0;
}

скажите пожалуйста 10 тест

Почему ваше решение не ловит TLE, если асимптотика O($n * max(a_i)$)

Асимптотика $O(n + max(a_i))$.

Главное построить массивы prefix и suffix "проходом слева направо"

10й тест огромный.