Cod sursa(job #2759305)

Utilizator Horis21Horia Radu Horis21 Data 16 iunie 2021 18:32:20
Problema SequenceQuery Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>

using namespace std;

const int N = 1 << 18;

struct node
{
    long long total, pref, suf, smax;
};

bool vis[N];
node t[N];

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

long long max(long long a, long long b, long long c)
{
    return max(a, max(b, c));
}

node combine(node x, node y)
{
    node ans;
    ans.total = x.total + y.total;
    ans.pref = max(x.pref, x.total + y.pref);
    ans.suf = max(y.suf, x.suf + y.total);
    ans.smax = max(x.smax, y.smax, x.suf + y.pref);
    return ans;
}


node q(int p, int l, int r, int a, int b)
{
    if (a <= l && r <= b) return t[p];
    int m = (l + r) / 2, nl = 2*p, nr = 2*p + 1;
    if (a <= m && b > m)
    {
        node q_l = q(nl, l, m, a, b);
        node q_r = q(nr, m+1, r, a, b);
        return combine(q_l, q_r);
    }
    if (a <= m) return q(nl, l, m, a, b);
    return q(nr, m+1, r, a, b);
}

void update(int p, int l, int r, int pos, int val)
{
    if (l == r)
    {
        t[p].pref = t[p].smax = t[p].suf = t[p].total = val;
        vis[p] = true;
        return;
    }
    int m = (l + r) / 2, nl = 2*p, nr = 2*p + 1;
    if (pos <= m) update(nl, l, m, pos, val);
    else update(nr, m + 1, r, pos, val);
    if (vis[nl] && vis[nr]) t[p] = combine(t[nl], t[nr]);
    else if (vis[nl]) t[p] = t[nl];
    else t[p] = t[nr];
    vis[p] = true;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int aux;
        cin >> aux;
        update(1, 1, n, i, aux);
    }
    for (int i = 0; i < m; i++)
    {
        int a, b;
        in >> a >> b;
        node ans = q(1, 1, n, a, b);
        cout << ans.smax << "\n";
    }
    return 0;
}