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


Есеп C. Квадраттардың қосындысы

Ограничение по времени:
1 second
Ограничение по памяти:
256 megabytes

Ұзындығы $n$ болатын екі массив берілген. Берілген массивке байланысты, сізге $q$ рет сұрақ қойылады. Сұрақтардың бәрінің үлгісі бірдей, тек сандары өзгереді. Әр сұрақта сізге белгілі бір аралықты анықтайтын $l$ және $r$ берілген. Берілген аралыққа кіретін бүкіл $a[i]$ мен $b[i]$-лардың айырмаларының квадраттарының қосындысын шығаруыңыз керек. $a[i]$ мына аралықта болуы керек: $a_l, a_{l+1}, \ldots, a_r$ $b[i]$ мына аралықта болуы керек: $b_l, b_{l+1}, \ldots, b_r$
Формат входного файла
Бірінші қатарда сізге екі сан берілген: $n, q, (1 \leq n, q \leq 100000)$\newline Екінші және үшінші қатарда, сәйкесінше, $a$ және $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;

}