Submission #796328

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796328	2023-07-28T09:43:56 Z	Johann	Tourism (JOI23_tourism)	C++14	7 / 100	108 ms	10376 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	72 ms	7304 KB	Output is correct
5	Correct	66 ms	7736 KB	Output is correct
6	Correct	64 ms	9472 KB	Output is correct
7	Correct	106 ms	10376 KB	Output is correct
8	Correct	108 ms	10340 KB	Output is correct
9	Correct	102 ms	10304 KB	Output is correct
10	Correct	102 ms	10368 KB	Output is correct
11	Correct	106 ms	10276 KB	Output is correct
12	Correct	85 ms	10276 KB	Output is correct
13	Correct	83 ms	10348 KB	Output is correct
14	Correct	83 ms	10316 KB	Output is correct
15	Correct	34 ms	7088 KB	Output is correct
16	Correct	75 ms	9932 KB	Output is correct
17	Correct	75 ms	4428 KB	Output is correct