Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
0 / 0 / 0
Регистрация: 02.10.2016
Сообщений: 2

Олимпиадная задача. Сумма на отрезке

26.10.2017, 23:03. Показов 8026. Ответов 0
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Есть следующая задача:
Есть массив целых чисел длины n = 2^24, изначально заполненных нулями. Вам нужно сперва обработать m случайных запросов вида "прибавление на отрезке". Затем обработать q случайных запросов вида "сумма на отрезке".

Формат входных данных
На первой строке числа m, q (1 ≤ m, q ≤ 2^24). На второй строке пара целых чисел a, b от 1 до 10^9, используемая в генераторе случайных чисел.
C++
1
2
3
4
5
6
unsigned int a, b; // даны во входных данных 
unsigned int cur = 0; // беззнаковое 32-битное число 
unsigned int nextRand() { 
  cur = cur * a + b; // вычисляется с переполнениями 
  return cur >> 8; // число от 0 до 224-1. 
}
Каждый запрос первого вида генерируется следующим образом:
C++
1
2
3
4
add = nextRand(); // число, которое нужно прибавить 
l = nextRand(); 
r = nextRand(); 
if (l > r) swap(l, r); // получили отрезок [l..r]
Каждый запрос второго вида генерируется следующим образом:
C++
1
2
3
l = nextRand(); 
r = nextRand(); 
if (l > r) swap(l, r); // получили отрезок [l..r]
Сперва генерируются запросы первого вида, затем второго.

Формат результата
Выведите сумму ответов на все запросы второго типа по модулю 2^32.

Пример
Входные данные: 5 5 13 239
Выходные данные: 811747796

Мой код, который ловит TL:
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
#include <iostream>
#include <vector>
 
using namespace std;
 
unsigned int a, b; //this block is described in the problem statement, so I've just copied it
unsigned int cur = 0;
unsigned int nextRand(){
    cur = cur * a + b;
    return cur >> 8;
}
 
int main() {
    const int n = 1 << 24;
    int m, q;
    unsigned int add, l, r;
    cin >> m >> q >> a >> b;
    vector<long long> segment(n + 1, 0);
    for (int i = 0; i < m; ++i) {
        add = nextRand(); //first type of queries, it is also described in statement
        l = nextRand();
        r = nextRand();
        if (l > r)
            swap(l, r);
        segment[l] += add;
        segment[r + 1] -= add; //"promise"
    }
    int curr = 0;
    unsigned partial_sum = 0;
    vector<unsigned int> v(n, 0);
    for (int i = 0; i < n; ++i){
        curr += segment[i];
        partial_sum += curr;
        v[i] = partial_sum;
    }
    unsigned sum = 0;
    for (int i = 0; i < q; ++i) {
        l = nextRand(); //second type of queries
        r = nextRand();
        if (l > r)
            swap(l, r);
        if (l > 0)
            sum += v[r] - v[l - 1];
        else
            sum += v[r];
    }
    cout << sum;
    return 0;
}
Коротко о том, что он делает. Я генерю числа, затем в вектор segment записываю "обещание" посчитать его потом, дальше в вектор v записываю частичные суммы на отрезке [0, i], из которых потом получаю ответ.
Как улучшить решение? Может, более эффективный алгоритм есть?
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
26.10.2017, 23:03
Ответы с готовыми решениями:

Олимпиадная задача Сумма простых
наприме мы вводим размер массива 3 потом сколько чисел надо сложить 2 а потом массив 6 5 7 и вы водитьса другой массив например 6+5=11...

Олимпиадная задача - сумма чисел меньших N, которые делятся на A или на B
Условие Ватсон поставил Рыбке простую задачу - найти сумму чисел меньших N, которые должны делиться или на A, или на B, и вывести ее...

Олимпиадная задача
Есть такая задачка: В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1, 3, 7, 11, 13, 17, ... Необходимо по номеру N определить...

0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
26.10.2017, 23:03
Помогаю со студенческими работами здесь

C++. Олимпиадная задача
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И если не правильный, то как исправить? Помогите найти ошибку....

Олимпиадная задача
Вот наткнулся сегодня на такую задачу: Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда...

Олимпиадная задача
Был в прошлом году на олимпиаде по программированию и там была такая задача: После запуска программы пользователь должен начать...

Олимпиадная задача
#include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;iostream&gt; using namespace std; int main() { unsigned int N; cout&lt;&lt;&quot;N=&quot;;...

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


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Новые блоги и статьи
Символические и жёсткие ссылки в Linux.
algri14 15.03.2026
Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это дополнительная запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru