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

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

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

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

03.06.2012, 12:07. Просмотров 539. Ответов 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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.06.2012, 12:07     Оптимизация времени выполнения
Посмотрите здесь:

Оптимизация [сокращение времени выполнения] - 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++
Такой вопрос- необходимо получить время выполнения процедуры сортировки массива. Для этого я использовал следующее выражение void...

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

ускорение времени выполнения программы - C++
здравствуйте. решал олимпиадную задачу: ...Он берет произвольное положительное число А и выписывает на доске арифметическую прогрессию...

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

Ошибка времени выполнения (terminate) - C++
вот этот код // на всякий случай привожу весь код, // т.к. не понимаю что именно вызывает ошибку // verylong.h #ifndef...

Измерение времени выполнения потока - C++
#include &quot;stdafx.h&quot; #include &lt;clocale&gt; #include &lt;math.h&gt; #include &lt;windows.h&gt; int l, m, n, geo, sum; DWORD WINAPI proizv...

функция определения времени выполнения - C++
подскажите пожалуйста есть ли в С++ функция замера времени исполнения?? суть такова - нужна было один алгоритм написаный на бейсике...

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

оценку времени выполнения алгоритма на С++ - C++
оценить время работы алгоритма для матриц размерностей от 5 на 5 (верхний предел может быть больше), результаты измерений записать в файл ...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1608 / 1000 / 118
Регистрация: 27.09.2009
Сообщений: 1,930
Завершенные тесты: 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;
}
valeriikozlov
Эксперт C++
4669 / 2495 / 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].
CLEO_ROCK
70 / 70 / 2
Регистрация: 22.05.2011
Сообщений: 528
05.06.2012, 21:33  [ТС]     Оптимизация времени выполнения #4
valeriikozlov, спасибо большое! отличный способ, все получилось. Время выполнения в прмерно 700-800мс
Yandex
Объявления
05.06.2012, 21:33     Оптимизация времени выполнения
Ответ Создать тему
Опции темы

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