Equal Beauty CodeChef SnackDown 2021 Round 1A Question The beauty of an (non-empty) array of integers is defined as the difference between its largest and smallest element. For example, the beauty of the array [2,3,4,4,6] is 6−2=4. An array A is said to be good if it is possible to partition the elements of A into two non-empty arrays B1 and B2 such that B1 and B2 have the same beauty. Each element of array A should be in exactly one array: either in B1 or in B2. For example, the array [6,2,4,4,4] is good because its elements can be partitioned into two arrays B1=[6,4,4] and B2=[2,4], where both B1 and B2 have the same beauty (6−4=4−2=2). You are given an array A of length N. In one move you can: Select an index i (1≤i≤N) and either increase Ai by 1 or decrease Ai by 1. Find the minimum number of moves required to make the array A good. Input Format The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follow. Each test
Yet Another SubSegment Sum Problem CodeChef SnackDown 2021 Advanced Practice Contest
Question
You are given two arrays A and B, each consisting of N integers.
You are also given M queries of the form Lj Rj Cj Dj. For each of these queries, we ask you to calculate the value of the sum of max{0, Ai × Cj - Bi × Dj} over i from Lj to Rj.
This is an on-line problem, so you won't get the next query unless you answer the current one.
Input
The first line of the input contains an integer N denoting the length of the arrays A and B.
The second line contains N space-separeted integer numbers, denoting the array A.
The third line contains N space-separated integer numbers, denoting the array B.
The fourth line contains an integer Q denoting the number of queries.
Each of the following Q lines will contain four space-separated integer numbers Lj Rj Cj Dj denoting the query.
This is an interactive problem. That means that you won't be able to read Lj Rj Cj Dj before you've answered the previous query. Please flush output buffer after you've output the answer to each query. In C++ it can be done with fflush(stdout) routine.
Output
For each query, output the answer on a separate line. Please flush standard output after answering each query.
Constraints
- 1 ≤ N, Q ≤ 105
- 0 ≤ Ai, Bi ≤ 106
- 1 ≤ Lj ≤ Rj ≤ N
- 0 ≤ Cj, Dj ≤ 106
Sample Input
5 1 2 3 4 5 5 4 3 2 1 3 1 5 1 1 1 5 1 2 1 5 2 1
Sample Output
6 3 18
Explanation
Example case 1. If we write out max{0, Ai × Cj - Bi × Dj}, we will get the following:
- In the first query: {0, 0, 0, 2, 4}. The sum is 6.
- In the second query: {0, 0, 0, 0, 3}. The sum is 3.
- In the third query: {0, 0, 3, 6, 9}. The sum is 18.
Program Code in C++
#include<bits/stdc++.h>
#define SZ(x) ((int(x.size())))
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 100*1000+10;
ll a[maxn], b[maxn], c, d, q, p[maxn];
ld val;
int zero, L, R, loc, n;
pair <ll, ll> P;
vector <pair <ld, int> > v[4 * maxn];
vector <pair <ll, ll> > ps[4 * maxn];
void ins (int x, int &l, int &r, int &ind)
{
v[x].push_back (make_pair (val, ind));
if (r - l == 1)
return;
int mid = (l + r) / 2;
if (ind < mid)
ins (2 * x + 1, l, mid, ind);
else
ins (2 * x + 2, mid, r, ind);
}
void bld (int x, int &l, int &r)
{
sort (v[x].begin(), v[x].end());
P = {0, 0};
ps[x].push_back (P);
for (int i = 0; i < SZ(v[x]); i++)
{
P = {P.first + a[v[x][i].second], P.second + b[v[x][i].second]};
ps[x].push_back (P);
}
if (r - l == 1)
return;
int mid = (l + r) / 2;
bld (2 * x + 1, l, mid);
bld (2 * x + 2, mid, r);
}
ll get (int x, int &l, int &r, int &ql, int &qr)
{
if (l >= qr || ql >= r)
return 0;
if (ql <= l && r <= qr)
{
loc = lower_bound (v[x].begin(), v[x].end(), make_pair (val, -1)) - v[x].begin();
return c * ps[x][loc].first - d * ps[x][loc].second;
}
int mid = (l + r) / 2;
return get (2 * x + 1, l, mid, ql, qr) + get (2 * x + 2, mid, r, ql, qr);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
p[i + 1] = p[i] + a[i];
}
for (int i = 0; i < n; i++)
{
cin >> b[i];
if (a[i] != 0)
{
val = (ld)b[i] / (ld)a[i];
ins (zero, zero, n, i);
}
}
bld (zero, zero, n);
cin >> q;
for (int i = 0; i < q; i++)
{
cin >> L >> R >> c >> d;
L--;
if (d == 0)
cout << c * (p[R] - p[L]) << endl;
else
{
val = (ld)c / (ld)d;
cout << get (zero, zero, n, L, R) << endl;
}
}
return 0;
}
Links
More information
CodeChef is one of the largest online coding platform and SnackDown is one of it's of grandest programs held ever year. SnackDown is a global programming event that invites programmers all over the world to participate in India's most prestigious multi-round programming competition. SnackDown is open to everyone who has a knack in programming.
This question that is Yet Another Subsegment Sum Problem is of CodeChef SnackDown 2021 Advanced Practice Contest. Here you will get a brief explanation of the problem and after reading the explanation if you are still stuck and have no clue to understand the problem then you can visit the solution of the question given above.
Hope you learnt something from this explanation and solution. Code it guys, practice coding more and more.
Comments
Post a Comment