답안 #889679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889679	2023-12-20T05:05:09 Z	vjudge1	Tourism (JOI23_tourism)	C++17	7 / 100	176 ms	13136 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];
    int cnt=0;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        if(u==v+1)cnt++;
        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

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

Subtask #2
0 / 5.0

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

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	3 ms	4444 KB	Output is correct
4	Correct	116 ms	10068 KB	Output is correct
5	Correct	112 ms	11348 KB	Output is correct
6	Correct	110 ms	12116 KB	Output is correct
7	Correct	176 ms	13136 KB	Output is correct
8	Correct	165 ms	12792 KB	Output is correct
9	Correct	164 ms	12728 KB	Output is correct
10	Correct	166 ms	12812 KB	Output is correct
11	Correct	164 ms	12628 KB	Output is correct
12	Correct	147 ms	12724 KB	Output is correct
13	Correct	147 ms	12628 KB	Output is correct
14	Correct	152 ms	12628 KB	Output is correct
15	Correct	71 ms	10012 KB	Output is correct
16	Correct	134 ms	12280 KB	Output is correct
17	Correct	110 ms	6916 KB	Output is correct