Submission #889673

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
889673	2023-12-20T05:01:21 Z	Aiperiii	Tourism (JOI23_tourism)	C++14	7 / 100	178 ms	13100 KB

tourism

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=1e5+5;
int mn[N*4],mx[N*4],c[N];
void build(int v,int tl,int tr){
    if(tl==tr){
        mn[v]=c[tl];
        mx[v]=c[tl];
    }
    else{
        int tm=(tl+tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        mn[v]=min(mn[v*2],mn[v*2+1]);
        mx[v]=max(mx[v*2],mx[v*2+1]);
    }
}
int get_mn(int v,int tl,int tr,int l,int r){
    if(r<tl or l>tr)return INT_MAX;
    if(l<=tl && tr<=r)return mn[v];
    int tm=(tl+tr)/2;
    return min(get_mn(v*2,tl,tm,l,r),get_mn(v*2+1,tm+1,tr,l,r));
}
int get_mx(int v,int tl,int tr,int l,int r){
    if(r<tl or l>tr)return INT_MIN;
    if(l<=tl && tr<=r)return mx[v];
    int tm=(tl+tr)/2;
    return max(get_mx(v*2,tl,tm,l,r),get_mx(v*2+1,tm+1,tr,l,r));
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);
    int n,m,qq;
    cin>>n>>m>>qq;
    vector <int> g[n+1];
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1;i<=m;i++){
        cin>>c[i];
    }
    
    build(1,1,m);
    while(qq--){
        int l,r;
        cin>>l>>r;
        cout<<get_mx(1,1,m,l,r)-get_mn(1,1,m,l,r)+1<<"\n";
    }
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	4444 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	4444 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	4444 KB	Output is correct
2	Correct	1 ms	4440 KB	Output is correct
3	Correct	2 ms	4444 KB	Output is correct
4	Correct	119 ms	10024 KB	Output is correct
5	Correct	117 ms	11344 KB	Output is correct
6	Correct	113 ms	12140 KB	Output is correct
7	Correct	165 ms	12728 KB	Output is correct
8	Correct	164 ms	12628 KB	Output is correct
9	Correct	173 ms	12728 KB	Output is correct
10	Correct	178 ms	12624 KB	Output is correct
11	Correct	164 ms	12608 KB	Output is correct
12	Correct	147 ms	12824 KB	Output is correct
13	Correct	165 ms	13100 KB	Output is correct
14	Correct	154 ms	12628 KB	Output is correct
15	Correct	78 ms	10072 KB	Output is correct
16	Correct	143 ms	12212 KB	Output is correct
17	Correct	116 ms	6824 KB	Output is correct