Submission #789336

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789336	2023-07-21T09:24:04 Z	이동현(#10044)	Tourism (JOI23_tourism)	C++17	0 / 100	122 ms	46704 KB

tourism

#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> way(n);
    for(int i = 1; i < n; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        way[x].push_back(y);
        way[y].push_back(x);
    }

    vector<int> a(m);
    for(int i = 0; i < m; ++i){
        cin >> a[i];
        --a[i];
    }

    vector<vector<int>> mx(m, vector<int>(20, -1));
    vector<vector<int>> mn(m, vector<int>(20, (int)1e9));
    for(int i = m - 1; i >= 0; --i){
        mx[i][0] = mn[i][0] = a[i];
        for(int j = 1; j < 20; ++j){
            mx[i][j] = mx[i][j - 1];
            mn[i][j] = mn[i][j - 1];
            if(i + (1 << j) < m){
                mx[i][j] = max(mx[i][j], mx[i + (1 << (j - 1))][j - 1]);
                mn[i][j] = min(mn[i][j], mn[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    while(q--){
        int l, r;
        cin >> l >> r;
        --l, --r;

        int up = -1, down = (int)1e9;
        for(int i = 19; i >= 0; --i){
            if(l + (1 << i) <= r + 1){
                up = max(up, mx[l][i]);
                down = min(down, mn[l][i]);
                l += (1 << i);
            }
        }

        cout << up - down + 1 << '\n';
    }
    
    return 0;
}

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
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	2 ms	1144 KB	Output is correct
4	Correct	99 ms	39584 KB	Output is correct
5	Correct	69 ms	28092 KB	Output is correct
6	Correct	89 ms	38712 KB	Output is correct
7	Correct	118 ms	46584 KB	Output is correct
8	Correct	122 ms	46640 KB	Output is correct
9	Correct	118 ms	46704 KB	Output is correct
10	Correct	118 ms	46668 KB	Output is correct
11	Correct	118 ms	46636 KB	Output is correct
12	Incorrect	89 ms	46648 KB	Output isn't correct
13	Halted	0 ms	0 KB	-