DCP-301: Balanced array Back to All Problems

Hard Data Structures > Segment Tree/Interval Tree


The **Buddu** define a **Balanced array** as follows: 1. An **empty** array is a Balanced array. 2. If {x1, x2, ..., xn} and {y1, y2, ..., ym} are Balanced arrays, then array {x1, x2, ..., xn, y1, y2, ..., ym} (their concatenation) also is a Balanced array. 3. If {x1, x2, ..., xn} — is a Balanced array, then array{ -v,x1, x2, ..., xn,v } also is a Balanced array, where v **(|v| > 0)** is an integer. For example, sequences {-5, -1,  1, -2,  2,  5} and {-6,  6} are Balanced arrays, and {2,  2} is not. You are given **Balanced array of N (1<=N<=10^5) integers, 1<=|array[i]|<=10^5**. You are given **Q (1<=Q<=50000)** queries. For each queries you will be given **Id (1<=Id<=N)** such that array[id] is **Positive always**. You have to tell **"Whether the array will be Balanced such that array[Id] is negative and you are allowed to change the sign of at most one element in other position except Id? "** See sample description for more details. Input: ------ Input starts with an integer **T** (1<=40), denoting the number of test cases. Each test case contains following information. The first line of the each test contains integer **N** [1 ≤ N ≤ 10^5]. The second line contains N integers: a1, a2, ..., aN [1 ≤ |array[i]| ≤ 10^5]. The third line of the contains integer **Q** [1 ≤ Q ≤ 50000]. The fourth line contains query values. Each query will contain Id such that [1<=Id<=N]. Output: ------- For each query output "**yes**" if it is possible to make **Balanced array** such that array value at position **Id** is negative(Must) and you can change sign of at most other element except Id.Otherwise print "**no**".See the samples for exact formatting Sample Input ------------ 1 8 -2 -1 1 2 -1 1 -1 1 4 3 4 6 8 Sample Output ------------- Case 1: no no yes no Sample Case Description ------------- For third query , `-2 -1 1 2 -1 -1 1 1` is valid


Problem Setter:

Bir Bahadur Khatri

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

10/24

Solve/Submission

Ranking

# User Language Timing
01 feodorv C 0.22s
02 khatribiru Cpp 0.41s
03 BishalG Cpp14 0.85s
04 ovis96 Cpp14 0.86s
05 boatinw99 Cpp14 1.10s
06 shikhar Cpp 1.35s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support