Тема: Час виконання програми
Привіт!
Є задача, написав для неї програму, яка працює правильно. Але E-Olymp видає помилку про ліміт часу. Можливо підкажете як можна оптимізувати алгоритм?
Задача:
Код:
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 200000;
const int QMAX = 200000;
int n, q;
void sort_arr(int list[]){
for(int step = n/2; step > 0; step /= 2)
{
for (int i = step; i < n; i += 1)
{
int j = i;
while(j >= step && list[j - step] < list[i])
{
swap(list[j], list[j - step]);
j-=step;
}
}
}
}
void request_first_x(int arr[], int x){
for (int i = 0; i<n; i++){
arr[i]+=x;
}
}
void request_second_k(int arr[], int k){
cout<<arr[k-1]<<endl;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
int a[NMAX];
int r[QMAX][2];
for (int i = 0; i < n; i++){
cin>>a[i];
}
sort_arr(a);
for (int i = 0; i < q; i++){
for (int j = 0; j < 2; j++){
cin>>r[i][j];
}
if (r[i][0] == 1) {
request_first_x(a, r[i][1]);
}
else if (r[i][0] == 2){
request_second_k(a, r[i][1]);
}
}
}