답안 #789336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	212 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	결과	실행 시간	메모리	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	-