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

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

Восстановить пароль Регистрация
 
CLEO_ROCK
 Аватар для CLEO_ROCK
66 / 66 / 2
Регистрация: 22.05.2011
Сообщений: 528
03.06.2012, 12:07     Оптимизация времени выполнения #1
Доброго времени суток. Есть следующая задача. Задача олимпиадная, потому учитывается время выполнения, нужно вложится в 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++
C++ Уменьшение времени выполнения цикла
C++ Ошибка времени выполнения.
функция определения времени выполнения C++
Подсчет времени выполнения функции C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1590 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,898
Завершенные тесты: 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++
 Аватар для valeriikozlov
4660 / 2486 / 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
 Аватар для CLEO_ROCK
66 / 66 / 2
Регистрация: 22.05.2011
Сообщений: 528
05.06.2012, 21:33  [ТС]     Оптимизация времени выполнения #4
valeriikozlov, спасибо большое! отличный способ, все получилось. Время выполнения в прмерно 700-800мс
Yandex
Объявления
05.06.2012, 21:33     Оптимизация времени выполнения
Ответ Создать тему
Опции темы

Текущее время: 00:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru