Banco do Faraó - Neps

#include <bits/stdc++.h>

#define SYNC ios::sync_with_stdio(0);
#define F first
#define S second
#define endl '\n'


using namespace std;

using ll = long long int;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using graph = vector<vi>;
const int INF = 0x3f3f3f3f;
const int MAXN = 199999;
const ll mod = 1000000007;
const double eps = 0.000000001;


int acc[MAXN];

struct data {
  int sum, pref, suff, ans, num_elem_sum, num_elem_pref, num_elem_suff, num_elem_ans;
};

data segtree[4*MAXN];

data make_data(int val) {
  data temp;
  temp.sum = temp.pref = temp.suff = temp.ans = val;
  temp.num_elem_sum = temp.num_elem_pref = temp.num_elem_suff = temp.num_elem_ans = 1;
  return temp;
}

data combine(data l, data r) {
  data temp;
  temp.sum = l.sum + r.sum;
  temp.num_elem_sum = l.num_elem_sum + r.num_elem_sum;
  if (l.pref > l.sum + r.pref) {
    temp.pref = l.pref;
    temp.num_elem_pref = l.num_elem_pref;
  } else {
    temp.pref = l.sum + r.pref;
    temp.num_elem_pref = l.num_elem_sum + r.num_elem_pref;
  }

  if (r.suff > l.suff + r.sum) {
    temp.suff = r.suff;
    temp.num_elem_suff = r.num_elem_suff;
  } else {
    temp.suff = l.suff + r.sum;
    temp.num_elem_suff = l.num_elem_suff + r.num_elem_sum;
  }

  if (max(l.ans, r.ans) > l.suff + r.pref) {
    if (l.ans > r.ans) {
      temp.ans = l.ans;
      temp.num_elem_ans = l.num_elem_ans;
    } else if (l.ans < r.ans) {
      temp.ans = r.ans;
      temp.num_elem_ans = r.num_elem_ans;
    } else {
      temp.ans = r.ans;
      temp.num_elem_ans = max(r.num_elem_ans, l.num_elem_ans);
    }
  } else if (max(l.ans, r.ans) < l.suff + r.pref) {
    temp.ans = l.suff + r.pref;
    temp.num_elem_ans = l.num_elem_suff + r.num_elem_pref;
  } else {
    temp.ans = l.suff + r.pref;
    temp.num_elem_ans = max(max(l.num_elem_ans, r.num_elem_ans), l.num_elem_suff + r.num_elem_pref);
  }

  return temp;

}

data combin(data l, data r) {
  data res;
  res.sum = l.sum + r.sum;
  res.pref = max(l.pref, l.sum + r.pref);
  res.suff = max(r.suff, r.sum + l.suff);
  res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
  return res;


}

void build(int node, int cl, int cr) {
  if (cl == cr) {
    segtree[node] = make_data(acc[cl]);
  } else {
    int mid = cl + (cr - cl)/2;
    build(node*2, cl, mid);
    build(node*2 + 1, mid+1, cr);
    segtree[node] = combine(segtree[node*2], segtree[node*2 + 1]);
  }
}

data max_sum(int node, int cl, int cr, int l, int r) {
  if (l > r) return make_data(-INF);

  if (cl == l && cr == r) {
    return segtree[node];
  }

  int mid = cl + (cr - cl)/2;

  data d1 = max_sum(node*2, cl, mid, l, min(r, mid));
  data d2 = max_sum(node*2 +1, mid+1, cr, max(l, mid+1), r);
  if (d1.ans == -INF) return d2;
  if (d2.ans == -INF) return d1;
  return combine(d1, d2);
}



int main() {
  SYNC
  int num_inst, num_acc, num_q;
  scanf("%d", &num_inst);
  while(num_inst--) {
    //memset(segtree, 0, sizeof(segtree));
    //memset(acc, 0, sizeof(acc));
    scanf("%d", &num_acc);
    for (int i = 0; i < num_acc; ++i) {
      scanf("%d", &acc[i]);
    }

    build(1, 0, num_acc-1);
    scanf("%d", &num_q);
    int l, r;
    while(num_q--) {
      scanf("%d %d", &l, &r);
      data ans = max_sum(1, 0, num_acc-1, l-1, r-1); //find the subsegment with the greater sum
      printf("%d %d\n", ans.ans, ans.num_elem_ans);
    }
  }
  return 0;
}