Submission #796328

#	Time	Username	Problem	Language	Result	Execution time	Memory
796328		Johann	Tourism (JOI23_tourism)	C++14	7 / 100	108 ms	10376 KiB

tourism

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, M, Q;
vi C, CM;
vvi adj;

struct segtree
{
    vi maxi;
    int size;
    void init(vi &A)
    {
        size = 1;
        while (size < sz(A))
            size *= 2;
        maxi.assign(2 * size, INT_MIN);
        for (int i = 0; i < sz(A); ++i)
            maxi[i + size] = A[i];
        for (int i = size - 1; i > 0; --i)
            maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]);
    }
    int query(int l, int r) { return query(l, r, 1, 0, size); }
    int query(int l, int r, int x, int lx, int rx)
    {
        if (l <= lx && rx <= r)
            return maxi[x];
        if (r <= lx || rx <= l)
            return INT_MIN;
        int m = (lx + rx) / 2;
        return max(query(l, r, 2 * x, lx, m), query(l, r, 2 * x + 1, m, rx));
    }
};
segtree segMax;
segtree segMin;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> Q;

    adj.resize(N);
    for (int i = 0, a, b; i < N - 1; ++i)
    {
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }

    C.resize(M), CM.resize(M);
    for (int i = 0; i < M; ++i)
    {
        cin >> C[i];
        --C[i];
        CM[i] = -C[i];
    }
    segMax.init(C);
    segMin.init(CM);

    for (int i = 0, l, r; i < Q; ++i)
    {
        cin >> l >> r;
        --l;
        int lx = -segMin.query(l, r);
        int rx = segMax.query(l, r);

        cout << rx - lx + 1 << "\n";
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41