Submission #1037852

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1037852	2024-07-29T09:13:40 Z	김은성(#10980)	Tourism (JOI23_tourism)	C++17	7 / 100	94 ms	10832 KB

tourism

#include <bits/stdc++.h>
using namespace std;
vector<int> graph[100009];
int a[100009], tree[1<<18], tree2[1<<18];
void settree(int v, int l, int r){
    if(l==r)
        tree[v] = a[l];
    else{
        int mid = (l+r)/2;
        settree(2*v, l, mid);
        settree(2*v+1, mid+1, r);
        tree[v] = min(tree[2*v], tree[2*v+1]);
    }
}
int query(int v, int l, int r, int s, int e){
    if(s<=l && r<=e)
        return tree[v];
    if(e<l || r<s)
        return 1234124323;
    int mid = (l+r)/2;
    return min(query(2*v, l, mid, s, e), query(2*v+1, mid+1, r, s, e));
}

void settree2(int v, int l, int r){
    if(l==r)
        tree2[v] = a[l];
    else{
        int mid = (l+r)/2;
        settree2(2*v, l, mid);
        settree2(2*v+1, mid+1, r);
        tree2[v] = max(tree2[2*v], tree2[2*v+1]);
    }
}
int query2(int v, int l, int r, int s, int e){
    if(s<=l && r<=e)
        return tree2[v];
    if(e<l || r<s)
        return -1234124323;
    int mid = (l+r)/2;
    return max(query2(2*v, l, mid, s, e), query2(2*v+1, mid+1, r, s, e));
}
int main(){
    int n, m, q, i, u, v;
    scanf("%d %d %d", &n, &m, &q);
    for(i=0; i<n-1; i++){
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    for(i=1; i<=m; i++){
        scanf("%d", &a[i]);
    }
    settree(1, 1, m);
    settree2(1,1,m);
    for(i=0; i<q; i++){
        scanf("%d %d", &u, &v);
        printf("%d\n", query2(1, 1, m, u, v) - query(1,1, m,u,v)+1);
    }
    return 0;
}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
tourism.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
tourism.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4956 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	4956 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	4956 KB	Output is correct
2	Correct	1 ms	4956 KB	Output is correct
3	Correct	2 ms	5072 KB	Output is correct
4	Correct	76 ms	7244 KB	Output is correct
5	Correct	69 ms	9300 KB	Output is correct
6	Correct	60 ms	9552 KB	Output is correct
7	Correct	94 ms	10580 KB	Output is correct
8	Correct	94 ms	10576 KB	Output is correct
9	Correct	94 ms	10732 KB	Output is correct
10	Correct	94 ms	10576 KB	Output is correct
11	Correct	94 ms	10832 KB	Output is correct
12	Correct	90 ms	10324 KB	Output is correct
13	Correct	83 ms	10320 KB	Output is correct
14	Correct	83 ms	10324 KB	Output is correct
15	Correct	31 ms	9376 KB	Output is correct
16	Correct	69 ms	10324 KB	Output is correct
17	Correct	75 ms	6300 KB	Output is correct