Submission #789191

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789191	2023-07-21T07:16:41 Z	반딧불(#10041)	Tourism (JOI23_tourism)	C++17	7 / 100	141 ms	11688 KB

tourism

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k, q;
vector<int> link[100002];
int arr[100002];

struct segTree{
    int treeMin[400002], treeMax[400002];
    void init(int i, int l, int r, int *arr){
        if(l==r){
            treeMin[i] = treeMax[i] = arr[l];
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, arr);
        init(i*2+1, m+1, r, arr);
        treeMin[i] = min(treeMin[i*2], treeMin[i*2+1]);
        treeMax[i] = max(treeMax[i*2], treeMax[i*2+1]);
    }
    int queryMin(int i, int l, int r, int s, int e){
        if(r<s||e<l) return INT_MAX;
        if(s<=l&&r<=e) return treeMin[i];
        int m = (l+r)>>1;
        return min(queryMin(i*2, l, m, s, e), queryMin(i*2+1, m+1, r, s, e));
    }
    int queryMax(int i, int l, int r, int s, int e){
        if(r<s||e<l) return INT_MIN;
        if(s<=l&&r<=e) return treeMax[i];
        int m = (l+r)>>1;
        return max(queryMax(i*2, l, m, s, e), queryMax(i*2+1, m+1, r, s, e));
    }
} tree;

int main(){
    scanf("%d %d %d", &n, &k, &q);
    for(int i=1; i<n; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        link[y].push_back(x);
    }

    for(int i=1; i<=k; i++) scanf("%d", &arr[i]);
    tree.init(1, 1, k, arr);
    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", tree.queryMax(1, 1, k, l, r) - tree.queryMin(1, 1, k, l, r) + 1);
    }
}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d %d %d", &n, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
tourism.cpp:47:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     for(int i=1; i<=k; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~
tourism.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 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	2 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	2 ms	2644 KB	Output is correct
2	Correct	2 ms	2652 KB	Output is correct
3	Correct	3 ms	2644 KB	Output is correct
4	Correct	88 ms	7368 KB	Output is correct
5	Correct	87 ms	8432 KB	Output is correct
6	Correct	78 ms	10036 KB	Output is correct
7	Correct	141 ms	10468 KB	Output is correct
8	Correct	124 ms	11688 KB	Output is correct
9	Correct	107 ms	11668 KB	Output is correct
10	Correct	124 ms	11628 KB	Output is correct
11	Correct	110 ms	11584 KB	Output is correct
12	Correct	91 ms	11384 KB	Output is correct
13	Correct	132 ms	11460 KB	Output is correct
14	Correct	92 ms	11396 KB	Output is correct
15	Correct	52 ms	7452 KB	Output is correct
16	Correct	82 ms	11256 KB	Output is correct
17	Correct	99 ms	6608 KB	Output is correct