HackerEarth Different queries problem solution

In this HackerEarth Different queries problem solution You are given an array A of size N. You have to perform Q queries on the array. Each of these queries belongs to the following types of queries:
  1. L R X : Add X to all elements in the range [L,R]
  2. L R X : Set the value of all elements in the range [L,R] to X
However, it is not mandatory to perform the queries in order. Your task is to determine the lexicographically largest array that can be obtained by performing all the Q queries.


HackerEarth Different queries problem solution


HackerEarth Different queries problem solution.

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

long long A[505];
vector< pair<int, pair<int, int> > > negative_add, positive_add, all_set;

void addQueries(vector< pair<int, pair<int, int> > > &X)
{
for(auto it : X)
{
int x = it.first;
int L = it.second.first, R = it.second.second;

for(int i=L; i<=R; i++)
A[i] += x;
}
}

void setQueries(vector< pair<int, pair<int, int> > > &X)
{
for(auto it : X)
{
int x = it.first;
int L = it.second.first, R = it.second.second;

for(int i=L; i<=R; i++)
A[i] = x;
}
}

int main()
{
int N, Q;
cin >> N >> Q;

for(int i=1; i<=N; i++)
cin >> A[i];

while(Q--)
{
int type, L, R, x;
cin >> type >> L >> R >> x;

if(type == 1)
{
if(x < 0)
negative_add.push_back({x, {L, R}});
else
positive_add.push_back({x, {L, R}});
}
else
all_set.push_back({x, {L, R}});
}

sort(all_set.begin(), all_set.end());

addQueries(negative_add);
setQueries(all_set);
addQueries(positive_add);

for(int i=1; i<=N; i++)
cout << A[i] << " ";
cout << "\n";

return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;
const int MAX = 505;
long long a[MAX];
vector<pair<int, pair<int, int>>> p1, p2, p3;

int main(int argc, char* argv[]) {
if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
if(argc == 3) freopen(argv[2], "w", stdout);
int n, q, type, l, r, x;
assert(cin >> n >> q);
assert(1 <= n and n <= 500);
assert(1 <= q and q <= 1e5);
for(int i = 1; i <= n; i++) {
assert(cin >> a[i]);
assert(-1e5 <= a[i] and a[i] <= 1e5);
}
for(int i = 0; i < q; i++) {
assert(cin >> type >> l >> r >> x);
assert(1 <= type and type <= 2);
assert(1 <= l and l <= r);
assert(l <= r and r <= n);
assert(-1e5 <= x and x <= 1e5);
if (type == 1) {
if (x < 0) p1.push_back({x, {l, r}});
else p3.push_back({x, {l, r}});
}
else p2.push_back({x, {l, r}});
}
sort(p2.begin(), p2.end());
for(auto p : p1) {
x = p.first;
l = p.second.first;
r = p.second.second;
for(int j = l; j <= r; j++) {
a[j] += x;
}
}
for(auto p : p2) {
x = p.first;
l = p.second.first;
r = p.second.second;
for(int j = l; j <= r; j++) {
a[j] = x;
}
}
for(auto p : p3) {
x = p.first;
l = p.second.first;
r = p.second.second;
for(int j = l; j <= r; j++) {
a[j] += x;
}
}
for(int i = 1; i <= n; i++) {
cout << a[i] << " \n"[i == n];
}
assert(!(cin >> n));
return 0;
}


Post a Comment

0 Comments