Ideone.com

fork download

copy

#include<iostream>
#include<algorithm>
#include<cstring> //For memset
 
#define MAX  101
#define inf 15008
using namespace std ;
 
int arr[MAX];
int tree[2*MAX + 1];
 
//function definition
//void update(int node, int a, int b, int i, int j , int value);
int query(int node , int a , int b , int i , int j);
 
void build_tree(int node, int a, int b);
 
//function to find the middle value
inline int getMid (int a , int b){
    return (a+b)/2;
}
 
//Find the maximum of three numbers
inline int max(int a , int b , int c){
    if (a > b){
        if(a > c)
            return a ;
        else 
            return c ;
    }
    else{
        if(b > c)
            return b ;
        else 
            return c ;
    }
}
 
//Build segment tree
void build_tree(int node , int a , int b){
    if (a > b){
        return ; // out of range
    }
    if(a == b){
        tree[node] = arr[a];
        return ;
    }
    int mid = getMid(a , b);
    build_tree(node*2 , a , mid);
    build_tree(node*2+1 , mid+1 , b );
    tree[node] = max(tree[node*2] + tree[node*2 + 1] , tree[node*2] , tree[node*2 + 1]);
}
 
//Query tree
int query(int node , int a , int b , int i , int j ){
    if(a > b || a > j || b < i)
        return -inf; // Out of range
 
    if(a >= i && b <= j) // Current segment is totally within range [i, j]
        return tree[node];
 
    int mid = getMid(a , b);
    int q1 = query(node*2, a, mid, i, j); // Query left child
    int q2 = query(1+node*2, mid + 1, b, i, j); // Query right child
 
    int res = max(q1, q2); // Return final result
 
    return res;
}
 
//Driver Program
int main()
{
    int n ,i , l , r , m ; 
    //cout << "Enter the number of elements in the array\t";
    cin >> n ;
 
    //Input
    for(i = 1 ;i<=n;i++){
        cin >> arr[i];
    }
    //initializing the array
    memset(tree , 0, sizeof(tree));
    //Build Tree
    build_tree(1 , 1, n);
    cin >> m ;
    while(m--){
        cin >> l >> r ;
        cout << query(1 , 1 , n , l , r) << endl;
    }
return 0 ;
}

I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGFsZ29yaXRobT4KI2luY2x1ZGU8Y3N0cmluZz4gLy9Gb3IgbWVtc2V0CgojZGVmaW5lIE1BWCAgMTAxCiNkZWZpbmUgaW5mIDE1MDA4CnVzaW5nIG5hbWVzcGFjZSBzdGQgOwoKaW50IGFycltNQVhdOwppbnQgdHJlZVsyKk1BWCArIDFdOwoKLy9mdW5jdGlvbiBkZWZpbml0aW9uCi8vdm9pZCB1cGRhdGUoaW50IG5vZGUsIGludCBhLCBpbnQgYiwgaW50IGksIGludCBqICwgaW50IHZhbHVlKTsKaW50IHF1ZXJ5KGludCBub2RlICwgaW50IGEgLCBpbnQgYiAsIGludCBpICwgaW50IGopOwoKdm9pZCBidWlsZF90cmVlKGludCBub2RlLCBpbnQgYSwgaW50IGIpOwoKLy9mdW5jdGlvbiB0byBmaW5kIHRoZSBtaWRkbGUgdmFsdWUKaW5saW5lIGludCBnZXRNaWQgKGludCBhICwgaW50IGIpewogICAgcmV0dXJuIChhK2IpLzI7Cn0KCi8vRmluZCB0aGUgbWF4aW11bSBvZiB0aHJlZSBudW1iZXJzCmlubGluZSBpbnQgbWF4KGludCBhICwgaW50IGIgLCBpbnQgYyl7CiAgICBpZiAoYSA+IGIpewogICAgICAgIGlmKGEgPiBjKQogICAgICAgICAgICByZXR1cm4gYSA7CiAgICAgICAgZWxzZSAKICAgICAgICAgICAgcmV0dXJuIGMgOwogICAgfQogICAgZWxzZXsKICAgICAgICBpZihiID4gYykKICAgICAgICAgICAgcmV0dXJuIGIgOwogICAgICAgIGVsc2UgCiAgICAgICAgICAgIHJldHVybiBjIDsKICAgIH0KfQoKLy9CdWlsZCBzZWdtZW50IHRyZWUKdm9pZCBidWlsZF90cmVlKGludCBub2RlICwgaW50IGEgLCBpbnQgYil7CiAgICBpZiAoYSA+IGIpewogICAgICAgIHJldHVybiA7IC8vIG91dCBvZiByYW5nZQogICAgfQogICAgaWYoYSA9PSBiKXsKICAgICAgICB0cmVlW25vZGVdID0gYXJyW2FdOwogICAgICAgIHJldHVybiA7CiAgICB9CiAgICBpbnQgbWlkID0gZ2V0TWlkKGEgLCBiKTsKICAgIGJ1aWxkX3RyZWUobm9kZSoyICwgYSAsIG1pZCk7CiAgICBidWlsZF90cmVlKG5vZGUqMisxICwgbWlkKzEgLCBiICk7CiAgICB0cmVlW25vZGVdID0gbWF4KHRyZWVbbm9kZSoyXSArIHRyZWVbbm9kZSoyICsgMV0gLCB0cmVlW25vZGUqMl0gLCB0cmVlW25vZGUqMiArIDFdKTsKfQoKLy9RdWVyeSB0cmVlCmludCBxdWVyeShpbnQgbm9kZSAsIGludCBhICwgaW50IGIgLCBpbnQgaSAsIGludCBqICl7CiAgICBpZihhID4gYiB8fCBhID4gaiB8fCBiIDwgaSkKICAgICAgICByZXR1cm4gLWluZjsgLy8gT3V0IG9mIHJhbmdlCgogICAgaWYoYSA+PSBpICYmIGIgPD0gaikgLy8gQ3VycmVudCBzZWdtZW50IGlzIHRvdGFsbHkgd2l0aGluIHJhbmdlIFtpLCBqXQogICAgICAgIHJldHVybiB0cmVlW25vZGVdOwoKICAgIGludCBtaWQgPSBnZXRNaWQoYSAsIGIpOwogICAgaW50IHExID0gcXVlcnkobm9kZSoyLCBhLCBtaWQsIGksIGopOyAvLyBRdWVyeSBsZWZ0IGNoaWxkCiAgICBpbnQgcTIgPSBxdWVyeSgxK25vZGUqMiwgbWlkICsgMSwgYiwgaSwgaik7IC8vIFF1ZXJ5IHJpZ2h0IGNoaWxkCgogICAgaW50IHJlcyA9IG1heChxMSwgcTIpOyAvLyBSZXR1cm4gZmluYWwgcmVzdWx0CiAgICAKICAgIHJldHVybiByZXM7Cn0KCi8vRHJpdmVyIFByb2dyYW0KaW50IG1haW4oKQp7CiAgICBpbnQgbiAsaSAsIGwgLCByICwgbSA7IAogICAgLy9jb3V0IDw8ICJFbnRlciB0aGUgbnVtYmVyIG9mIGVsZW1lbnRzIGluIHRoZSBhcnJheVx0IjsKICAgIGNpbiA+PiBuIDsKCiAgICAvL0lucHV0CiAgICBmb3IoaSA9IDEgO2k8PW47aSsrKXsKICAgICAgICBjaW4gPj4gYXJyW2ldOwogICAgfQogICAgLy9pbml0aWFsaXppbmcgdGhlIGFycmF5CiAgICBtZW1zZXQodHJlZSAsIDAsIHNpemVvZih0cmVlKSk7CiAgICAvL0J1aWxkIFRyZWUKICAgIGJ1aWxkX3RyZWUoMSAsIDEsIG4pOwogICAgY2luID4+IG0gOwogICAgd2hpbGUobS0tKXsKICAgICAgICBjaW4gPj4gbCA+PiByIDsKICAgICAgICBjb3V0IDw8IHF1ZXJ5KDEgLCAxICwgbiAsIGwgLCByKSA8PCBlbmRsOwogICAgfQpyZXR1cm4gMCA7Cn0=

Runtime error #stdin #stdout 0.04s 3416KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/FqZ6Zq

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language