Районная олимпиада по информатике. 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 )

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

AC

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

#include<iostream>
#define ll long long int
using namespace std;
int main(){
	ll n,q,a[101000],b[101000],l,r;
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		cin>>b[i];
		a[i]-=b[i];	
		a[i]=a[i]*a[i]+a[i-1];
	}
	while(q--){
		cin>>l>>r;
		cout<<a[r]-a[l-1]<<"\n";
	}
}

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin >> n >> q;
    ll a[n+1];
    a[0]=0;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++) {
        ll cur;
        cin >> cur;
        a[i] -= cur;
    }
    ll s[n+1];
    s[0] = 0;
    for (int i=1; i<=n; i++) s[i] = s[i-1] + a[i]*a[i];

    for (int j=1; j<=q; j++) {
        int l,r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << '\n';
    }
    return 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;
}

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

#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;
}

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

with open('input') as file:

    inner = file.readlines()
    input, data = list(), list()
    
    for line in range(0, len(inner)):
        res = inner[line].split('\n')[0]

        if line == 0: data.append(res.split()) 

        elif line >= len(inner) - int(data[0][1]): 
            data.append(res.split())  

        else: input.append(res.split())              

output, results = list(), list()

for query in range(1, len(data)): 

    for task in range(0, len(data[query])):

        output.append((int(input[0][task + 1]) - int(input[1][task + 1])) ** 2)

    result = 0

    for num in output: result += int(num)

    results.append(str(result))

    output.clear()

with open('output', 'w') as file: file.write('\n'.join(results))

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

//                                                              ۡمِ ٱللهِ ٱلرَّحۡمَـٰنِ ٱلرَّحِيمِ‎
//created by --------> Aslan Nesipbay;

#include<bits/stdc++.h>

// instagram.com/aslandoos
// vk.com/noone_knows_me

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef stringstream SS;
typedef pair< ll, ll > pll;

#define andy_panda vector
#define tumaniyo pll

const ll N = 2e5+5;
const ll NN = 105;
const ll MAX = 2e5 + 123;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

ll n, a[ N ], b[ N ], f[ N ];

void hajime()
{
    ll l, r;
    cin >> l >> r;
    cout << f[ r ] - f[ l - 1 ] << '\n';
}

int main()
{
    ll miyagi = 1;
    cin >> n >> miyagi;
    for( ll i = 1; i <= n; i ++ ) cin >> a[ i ];
    for( ll i = 1; i <= n; i ++ )
    {
        cin >> b[ i ];
        f[ i ] = ( max( a[ i ], b[ i ] ) - min( a[ i ], b[ i ] ) ) * ( max( a[ i ], b[ i ] ) - min( a[ i ], b[ i ] ) );
        f[ i ] += f[ i - 1 ];
    }
    while( miyagi -- ) hajime();
}

Зачем указывать на соц сети?

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(int) 1e5+500;
ll a[maxn],b[maxn];
int main() {
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++)
	cin>>a[i];
	for (int i=1;i<=n;i++) {
		cin>>b[i];
		a[i]=(a[i]-b[i])*1ll*(a[i]-b[i]);
		a[i]+=a[i-1];
	}
	while(m--) {
		int l,r;
		cin>>l>>r;
		cout<<a[r]-a[l-1]<<endl;
	}
	return 0;
}

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

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair < pii, int > piii;
typedef pair <ll, ll> pll;
typedef pair < pll, ll > plll;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;
typedef vector < pll > vll;
typedef set < int > si;
const int N = 1e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

ll n, q, a[N], b[N];
ll c[N], t[N];

void input() {
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++) {
		cin >> b[i];
		c[i] = (a[i] - b[i]) * (a[i] - b[i]);
		t[i] = t[i - 1] + c[i];
	}
}

ll sum(int l, int r) {
	return (t[r] - t[l - 1]);
}

void solve() {
	int l, r;
	cin >> l >> r;
	cout << sum(l, r) << "\n";
}

int main () {
	start
	input();
	while(q--) {
		solve();
	}
	return 0;
}

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

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;
int main(){
	speed;
	int n, q;
	cin >> n >> q;
	long long a[n + 1], save[n + 1], b[n + 1];
	save[0] = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++){
		cin >> b[i];
		a[i] = (a[i] - b[i]) * (a[i] - b[i]);
	}
	for(int i = 1; i <= n; i++){
		save[i] = save[i - 1] + a[i];
	}
	for(int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		cout << save[r] - save[l - 1] << endl;
	}	
}