1

Тема: Час виконання програми

Привіт!
Є задача, написав для неї програму, яка працює правильно. Але E-Olymp видає помилку про ліміт часу. Можливо підкажете як можна оптимізувати алгоритм?
Задача:

Прихований текст

https://replace.org.ua/uploads/images/7153/b8919bb54c1fe782f013c7e6cb6aad9d.jpg

Код:

#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]);
        }
    }

}

2

Re: Час виконання програми

Збільшення усіх чисел завжди на одну величину. Не треба все збільшувати, просто запам'ятовуйте, на скільки все мало змінитися, і додавайте перед виведенням.

3

Re: Час виконання програми

Дякую!