Submission #829295

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
829295	2023-08-18T08:23:57 Z	Hanksburger	Tourism (JOI23_tourism)	C++17	7 / 100	99 ms	11740 KB

tourism

#include <bits/stdc++.h>
using namespace std;
int mx[400005], mn[400005], c[100005];
vector<int> adj[100005];
void build(int i, int l, int r)
{
    if (l==r)
    {
        mx[i]=mn[i]=c[l];
        return;
    }
    int mid=(l+r)/2;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
    mx[i]=max(mx[i*2], mx[i*2+1]);
    mn[i]=min(mn[i*2], mn[i*2+1]);
}
int qryMx(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<=qr)
        return mx[i];
    int mid=(l+r)/2, res=0;
    if (l<=qr && ql<=mid)
        res=max(res, qryMx(i*2, l, mid, ql, qr));
    if (mid<qr && ql<=r)
        res=max(res, qryMx(i*2+1, mid+1, r, ql, qr));
    return res;
}
int qryMn(int i, int l, int r, int ql, int qr)
{
    if (ql<=l && r<=qr)
        return mn[i];
    int mid=(l+r)/2, res=1e9;
    if (l<=qr && ql<=mid)
        res=min(res, qryMn(i*2, l, mid, ql, qr));
    if (mid<qr && ql<=r)
        res=min(res, qryMn(i*2+1, mid+1, r, ql, qr));
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i=1; i<n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i=1; i<=m; i++)
        cin >> c[i];
    build(1, 1, m);
    for (int i=1; i<=q; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << qryMx(1, 1, m, l, r)-qryMn(1, 1, m, l, r)+1 << '\n';
    }
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	2644 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	2644 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	2644 KB	Output is correct
2	Correct	2 ms	2680 KB	Output is correct
3	Correct	3 ms	2644 KB	Output is correct
4	Correct	72 ms	9128 KB	Output is correct
5	Correct	64 ms	8752 KB	Output is correct
6	Correct	62 ms	10348 KB	Output is correct
7	Correct	98 ms	11704 KB	Output is correct
8	Correct	96 ms	11640 KB	Output is correct
9	Correct	96 ms	11644 KB	Output is correct
10	Correct	99 ms	11740 KB	Output is correct
11	Correct	96 ms	11604 KB	Output is correct
12	Correct	88 ms	11464 KB	Output is correct
13	Correct	86 ms	11460 KB	Output is correct
14	Correct	86 ms	11408 KB	Output is correct
15	Correct	34 ms	7420 KB	Output is correct
16	Correct	68 ms	11368 KB	Output is correct
17	Correct	81 ms	6620 KB	Output is correct