Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
CLEO_ROCK
70 / 70 / 2
Регистрация: 22.05.2011
Сообщений: 528
#1

Оптимизация времени выполнения - C++

03.06.2012, 12:07. Просмотров 559. Ответов 3
Метки нет (Все метки)

Доброго времени суток. Есть следующая задача. Задача олимпиадная, потому учитывается время выполнения, нужно вложится в 1секунду. Мой код на сервере работает 1,014 с. Никак не могу уменшыть время выполнения. Помогите кто может. Условие и мой код ниже.

Условие
Последовательность an задается следующей формулой: an = n2 mod 12345 + n3 mod 23456.

Требуется много раз отвечать на запросы следующего вида:

найти разность между максимальным и минимальным значением среди элементов ai, ai+1, ..., aj;
присвоить элементу ai значение j.

Технические условия
Входные данные

Первая строка содержит натуральное число k (k ≤ 100 000) - количество запросов. Следующие k строк содержат запросы, по одному в строке. Запрос номер i описывается двумя целыми числами xi, yi.

Если xi > 0, то требуется найти разность между максимальным и минимальным значением среди элементов axi...ayi. При этом 1 ≤ xi ≤ yi ≤ 100 000.

Если xi < 0, то требуется присвоить элементу a-xi значение yi. При этом -100 000 ≤ xi ≤ -1 и |yi| ≤ 100 000.

Выходные данные

Для каждого запроса первого типа требуется вывести в отдельной строке разность между максимальным и минимальным значением на соответствующем отрезке.

Пример входных данных
7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3

Пример выходных данных
34
68
250
234
1

Мой код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <fstream>
 
using namespace std;
 
__int64 a[100001];
ofstream out("output.txt");
 
int main()
{
for(__int64 i=1;i<100001;++i)
{
a[i]=(i*i) % 12345 + (i*i*i) % 23456;
 
}
 
int  min, max;
ifstream in("input.txt");
int kst=0,x=0,y=0;
in>>kst;
 
 
for(int i=0;i<kst;++i)
{
in>>x>>y;
if(x>0)
{
    max=min=a[x];
    for(int j=x;j<=y;++j)
    {
        if(a[j]<min)
        {
            min=a[j];
            continue;
        }
 
        if(a[j]>max)
            max=a[j];
    }
    
    out<<(max-min)<<"\n";
 
//diff(x,y);
}
else 
{
  a[x*(-1)]=y;
}
 
}
in.close ();
out.close();
 
return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2012, 12:07
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Оптимизация времени выполнения (C++):

Оптимизация [сокращение времени выполнения] - C++
Здравствуйте, стояла такая задача: Была сделана следующая программа: #include &lt;iostream&gt; using namespace std; int lucky(int...

Оптимизация [сокращение времени выполнения] - C++
Всем привет! В общем стояла такая задача: Посчитать среднее количество букв в предложении, состоящем из символов &quot;A-Z&quot;, &quot;a-z&quot;, &quot;0-9&quot;,...

Ошибка времени выполнения. - C++
Вот код: void Add_Kod ( _kod*&amp; KodBuf, int a, char* buf, char* buf2) { if(a==1) { KodBuf = new _kod; KodBuf.ch = *(buf);...

Ошибка времени выполнения - C++
Я пишу проэкт в Visual Studia 2008 на C++. У меня есть несколько проблем. Во-первых, когда я собираю финальную версию (release) и...

Измерение времени выполнения - C++
Подскажите пожалуйста как измерить время выполнения чего-то с наносекундной точностью. std::chrono::high_resolution_clock::time_point...

Подсчет времени выполнения функции - C++
Делаю 2 вида сортировки, не знаю как подсчитать их время. #include &lt;iostream&gt; #include &lt;time.h&gt; #include &lt;conio.h&gt; using namespace...

3
Nick Alte
Эксперт С++
1639 / 1011 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
03.06.2012, 14:53 #2
Вот могу идейку подбросить для дальнейшего осмысления.
Вывод квадратов натуральных чисел от 1 до 20:
C++
1
2
3
4
5
6
7
8
9
10
11
void squares1()  // Прямолинейный подход
{
    for(int i=1; i<20; ++i)
        cout << i*i << endl;
}
 
void squares2()  // Оптимизированный алгоритм
{
    for(int cv = 1, delta = 3; cv <= 400; cv += delta, delta += 2)
        cout << cv << endl;
}
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.06.2012, 21:35 #3
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
Мой код на сервере работает 1,014 с.
это не значит, что не хватает всего 0,014 с, вполне возможно что тестирующая система просто прерывает дальнейшую проверку при превышении времени выполнения уже на 0,014 с (я с таким сталкивался).
Nick Alte предложил хороший способ, но этим время сильно не выиграешь. Основная причина TL кроется здесь:
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
k (k ≤ 100 000)
Цитата Сообщение от CLEO_ROCK Посмотреть сообщение
Если xi > 0, то .... При этом 1 ≤ xi ≤ yi ≤ 100 000.
Т.е. может быть тест(ы), когда нужно около 100 000*100 000 итераций. Ни в какую секунду не влезет.
Предлагаю такой вариант:
завести еще один массив для хранения элементов типа структур. Каждый элемент такого массива будет хранить данные о диапазоне размером 1000 элементов. Т.е. элемент [0] такого массива будет хранить данные об элементах массива a[1]..a[1000]. Элемент [1] такого массива будет хранить данные об элементах массива a[1001]..a[2000]. И т.д. А хранить в каждом элементе такого массива нужно только минимальное и максимальное значение масива a[] в этом диапазоне.
Заполнение такого массива можно сделать на этапе заполнения массива a[].
Когда xi < 0, то нужно не только заменить значение в a[] но и посмотреть, не нужно ли менять значение min max в новом массиве для соответствующего диапазона.
Когда xi > 0, то искать максимальный и минимальный элемент нужно в новом массиве, и в a[] - в оставшихся кусочках, которые полностью не покрыты новым массивом.
Например xi=255, yi=6031:
- сначало минимальный и максимальный элемент ищем в новом массиве с [1] по [6] а потом ищем в массиве a[] с a[255] по a[1000] и с a[6001] по a[6031].
1
CLEO_ROCK
70 / 70 / 2
Регистрация: 22.05.2011
Сообщений: 528
05.06.2012, 21:33  [ТС] #4
valeriikozlov, спасибо большое! отличный способ, все получилось. Время выполнения в прмерно 700-800мс
0
05.06.2012, 21:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2012, 21:33
Привет! Вот еще темы с ответами:

Контроль времени выполнения программы - C++
Добрый день. У меня маленькая проблемка. Есть задача. Задача А - Гистограмма Ограничение времени: 1 с Ограничение памяти: 1024 M ...

Подсчет времени выполнения сортировки - C++
Подскажите, пожалуйста, как написать в программе, чтобы подсчитывало время выполнения сортировки? Там как-то надо ввести &quot;clock time&quot; ...

Определение времени выполнения кода - C++
Нужно определить сколько выполняется тот или иной цикл, подскажите поз, как это сделать

Уменьшение времени выполнения цикла - C++
Нужна помощь, мне надо засечь время выполнения цикла, который инициализирует элементы массива. А потом надо как-то развернуть цикл и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru