D_MAD - Editorial

editorial
1

PROBLEM LINK:

Practice
Contest

Author: rocknot
Tester: yogesh_5326
Editorialist: rocknot

DIFFICULTY:

EASY-MEDIUM.

PREREQUISITES:

Query optimization

PROBLEM: Dreams of Madness

You are given length of array N you need to create array arr[] of N integers having all the elements {0} and perform Q queries on it. Each query consist of three integers l,r,A
you need to add value of A to the elements of the array arr[] from l(th) element to r(th) element.

for each querry if A is even add A to all elements of array arr[] from l to r
if A is odd add from l to r according to given pattern A,A+1,A,A-1,A,A+1…..

You need to print the array arr[] after performing all the queries.

EXPLANATION:

For each query add value of A to l(th) element and -A to r+1(th) element and iterate through all the elements of the array and add the value of [i]th element of array to [i+1]th element.

For odd values of A create an temp array with all values initialized to 0 and for each odd query add pattern 0,1,0,-1,0,1,-1… in all the elements of temp array and after performing all the queries add all the elements of temp array to the main array.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        int N,Q;
        cin>>N;
        cin>>Q;
        int arr[N]={0},arr2[N]={0};
        int l,r,A;
        while(Q--){
            cin>>l>>r>>A;
            arr[l-1]+=A;
            if(r<N){
            arr[r]-=A;
            }
            if(A%2!=0){
                bool flag=true;
                for(int i=l;i<r;i+=2){
                    if(flag){
                    arr2[i]+=1;
                    flag=false;
                    }else{
                    arr2[i]-=1;
                    flag=true;
                    } 
              }
         }
    }
    for(int i=1;i<N;i++){
        arr[i]+=arr[i-1];
        arr[i-1]+=arr2[i-1];
    }
    for(int i=0;i<N;i++){
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
}
return 0;

}