Ускорение кода

@viktorgrin · Регистрация: 29.05.2018

Author24 — интернет-сервис помощи студентам

Ребят помогите ускорить код. Создаётся вектор на 100000001. Далее приходит n пар - начало и конец. Нужно добавлять единички к элементам начиная с индекса старт, заканчивая на индексе конец. Потом найти максимальный элемент. Сейчас буквально сотых долей секунды не хватает чтобы пройти тест

C++

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
int main(){
 
    vector <short int> mas(10000001);
    int n, st, end;
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> st >> end;
        for (auto it = mas.begin() + st; it != mas.begin() + end + 1; ++it)
            {
                *it += 1;
            }   
    }
    
    cout << std::distance(mas.begin(), std::max_element(mas.begin(), mas.end()));
    return 0;
}

@alkl · 10.12.2018, 21:49

Выкинуть вектор и заменить на обычный массив.

@VTsaregorodtsev · 10.12.2018, 21:51

не вычисляйте на КАЖДОЙ итерации внутреннего цикла ОДНО И ТО ЖЕ значение выражения mas.begin() + end + 1.
Вычислите его до цикла, сохраните в переменную и используйте её.

@NePascalist · 10.12.2018, 21:54

Ускорители ввода и вывода

C++

1
2
3

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

@Manowar · 10.12.2018, 22:09

std::iota

@alkl 119 / 94 / 35 Регистрация: 18.12.2012 Сообщений: 654
	10.12.2018, 21:49	2
	Выкинуть вектор и заменить на обычный массив. 0

@VTsaregorodtsev 1487 / 1414 / 240 Регистрация: 19.02.2010 Сообщений: 3,916
	10.12.2018, 21:51	3
	не вычисляйте на КАЖДОЙ итерации внутреннего цикла ОДНО И ТО ЖЕ значение выражения mas.begin() + end + 1. Вычислите его до цикла, сохраните в переменную и используйте её. 0

@Manowar 1718 / 567 / 187 Регистрация: 12.03.2016 Сообщений: 2,169
	10.12.2018, 22:09	5
	std::iota 0