Algorithmic-Problems/matchsticks.cpp at main · pi34/Algorithmic-Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// https://www.codechef.com/problems/MSTICK

#include <iostream>
#include <vector>

using namespace std;

vector<int> b(100005);
vector<int> segTreeMin(400020);
vector<int> segTreeMax(400020);

void construct (int l, int r, int pos) {
    if (l == r) {
        segTreeMin[pos] = b[l];
        segTreeMax[pos] = b[l];
        return;
    }
    int mid = (l+r)/2;
    construct(l, mid, pos*2);
    construct(mid+1, r, pos*2+1);
    segTreeMin[pos] = min(segTreeMin[pos*2], segTreeMin[pos*2+1]);
    segTreeMax[pos] = min(segTreeMax[pos*2], segTreeMax[pos*2+1]);
}

int minT (int l, int r, int pos, int q1, int q2) {
    if (q2 <= l || q1 >= r) {
        return INT_MAX;
    }
    if (q1 <= l && q2 >= r) {
        return segTreeMin[pos];
    }
    int mid = (l+r)/2;
    return min(minT(l, mid, pos, q1, q2), minT(mid+1, r, pos, q1, q2));
}

int maxT (int l, int r, int pos, int q1, int q2) {
    if (q2 <= l || q1 >= r) {
        return INT_MIN;
    }
    if (q1 <= l && q2 >= r) {
        return segTreeMax[pos];
    }
    int mid = (l+r)/2;
    return max(maxT(l, mid, pos, q1, q2), maxT(mid+1, r, pos, q1, q2));
}

int main ()
{
    int n;
    cin >> n;

    int b[n];
    for (int i = 1; i <= n; i++) cin >> b[i];

    int q;
    cin >> q;

    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;

        int m = minT (1, n, 0, l, r);
        int M = maxT (1, n, 0, l, r);
        int Md = max(maxT (1, n, 0, 1, l-1), maxT (1, n, 0, r+1, n));

        cout << (m+max((M-m)/2, Md));

    }
}