Районная олимпиада по информатике. 2018-2019 учебный год. 8-11 классы


Задача C. Сумма квадратов

Ограничение по времени:
1 секунда
Ограничение по памяти:
256 мегабайт

Даны два массива целых чисел длинны $n$. Даются $q$ запросов. Каждый запрос состоит из чисел $l$ и $r$, после каждого запроса требуется вывести чему равна сумма квадратов разностей чисел $a[i]$ и $b[i]$ где $i$= $l$, $l$+1,.., $r$.
Формат входного файла
Первая строка содержит числа $n, q, (1 \leq n, q \leq 100000)$\newline Вторая строка содержит массив n целых чисел(массив a)\newline Вторая строка содержит массив n целых чисел(массив b)\newline $(-100000 \leq a[i], b[i] \leq 100000)$, $i$ = 1, 2, ... , $n$\newline Следующие $q$ строк содержат числа $l, r, (1 \leq l \leq r \leq n)$ Система оценки:\newline Для 40\% тестов - $(1 \leq n, q \leq 100)$\newline Для 60\% тестов - $(1 \leq n, q \leq 100000)$
Формат выходного файла
В каждой строке выведите ответы на запросы
Пример:
Вход
3 1
1 0 5
1 2 3
2 3
Ответ
8
( Alikhan Okas )
посмотреть в олимпиаде

Комментарий/решение:

  -2
2018-12-14 12:19:36.0 #

AC

показать/скрыть код

  0
2019-01-08 21:02:02.0 #

показать/скрыть код

  0
2019-01-08 21:14:48.0 #

показать/скрыть код

  0
2019-03-07 18:49:39.0 #

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

long long int t[4 * 100000];

void build(int v, int vl, int vr, long long int a[]){

if(vl == vr) {

t[v] = a[vl];

return;

}

int vm = vl + (vr - vl) / 2;

build(2*v + 1, vl, vm, a);

build(2*v + 2, vm + 1, vr, a);

t[v] = t[2*v + 1] + t[2*v + 2];

}

long long query(int v, int vl, int vr, int l, int r){

if(r < vl || vr < l) return 0;

if(l <= vl && vr <= r) return t[v];

int vm = vl + (vr - vl) / 2;

long long int ql = query(2 * v + 1, vl, vm, l, r);

long long int qr = query(2 * v + 2, vm + 1, vr, l, r);

return ql + qr;

}

int main()

{

ios::sync_with_stdio(false);

long long int a[100000];

int aSize, q;

cin >> aSize >> q;

for(int i = 0; i < aSize; i++){

cin >> a[i];

} for(int i = 0; i < aSize; i++){

int b;

cin >> b;

a[i] = pow((a[i] - b), 2);

}

build(0, 0, aSize - 1, a);

for(int i = 0; i < q; i++){

int l, r;

cin >> l >> r;

cout << query(0, 0, aSize - 1, l - 1, r - 1) << endl;

}

return 0;

}