답안 #836130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836130	2023-08-24T07:46:37 Z	josanneo22	Tourism (JOI23_tourism)	C++17	7 / 100	171 ms	28348 KB

tourism

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define ar array

/*tourism
subtask 1&2: make root at l[i] then just find number of nodes passed through
subtask 3: since it is a chain, we just have to find max(c[l...r])-min(c[l...r])+1
*/
const int inf=1e18;
struct yl{
	int l,r,val;
};
struct seg_mx{
	vector<yl> tr;
	vector<int> C;
	seg_mx(){}
	seg_mx(int n,vector<int> &c){
		int S=4*n+600; C=c;
		tr.resize(S);
		build(1,1,n);
	}
	void build(int p,int l,int r){
		tr[p].l=l; tr[p].r=r;
		if(l==r){ tr[p].val=C[l]; return;}
		int mid=(l+r)>>1;
		build(p<<1,l,mid); build(p<<1|1,mid+1,r);
		tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
		return;
	}
	int query(int p,int l,int r){
		if(tr[p].l>r || tr[p].r<l) return -inf;
		if(l<=tr[p].l && tr[p].r<=r) return tr[p].val;
		return max(query(p<<1,l,r),query(p<<1|1,l,r));
	}
};

struct seg_mn{
	vector<yl> tr;
	vector<int> C;
	seg_mn(){}
	seg_mn(int n,vector<int> &c){
		int S=4*n+600; C=c;
		tr.resize(S);
		build(1,1,n);
	}
	void build(int p,int l,int r){
		tr[p].l=l; tr[p].r=r;
		if(l==r){ tr[p].val=C[l]; return;}
		int mid=(l+r)>>1;
		build(p<<1,l,mid); build(p<<1|1,mid+1,r);
		tr[p].val=min(tr[p<<1].val,tr[p<<1|1].val);
		return;
	}
	int query(int p,int l,int r){
		if(tr[p].l>r || tr[p].r<l) return inf;
		if(l<=tr[p].l && tr[p].r<=r) return tr[p].val;
		return min(query(p<<1,l,r),query(p<<1|1,l,r));
	}
};

void solve(){
	int n,m,q; cin>>n>>m>>q;
	vector<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);
	}
	vector<int> c(m+1),d(n+1);
	for(int i=1;i<=m;i++) cin>>c[i];
	seg_mx mx(m,c); 
	seg_mn mn(m,c);
	auto ans=[&](int l,int r){
		int rr=mx.query(1,l,r);
		int ll=mn.query(1,l,r);
		cout<<rr-ll+1<<'\n';
	};
	while(q--){
		int l,r; cin>>l>>r;
		ans(l,r);
	}
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	clock_t tStart = clock();
	int local=0,multi=0,debug=1,tt=1;
	if(local){
	    freopen("input.txt","r",stdin);
	    freopen("output.txt","w",stdout);
	}	
	if(multi) cin>>tt;
	for(int i=1;i<=tt;i++){
		if(debug && multi && local) cout<<"样例 "<<i<<'\n';
		solve();
 	}
	fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}

Compilation message

tourism.cpp: In function 'int main()':
tourism.cpp:96:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |      freopen("input.txt","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:97:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |      freopen("output.txt","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	2 ms	724 KB	Output is correct
4	Correct	106 ms	22920 KB	Output is correct
5	Correct	87 ms	17676 KB	Output is correct
6	Correct	111 ms	23660 KB	Output is correct
7	Correct	171 ms	28236 KB	Output is correct
8	Correct	134 ms	28348 KB	Output is correct
9	Correct	146 ms	28340 KB	Output is correct
10	Correct	154 ms	28340 KB	Output is correct
11	Correct	157 ms	28308 KB	Output is correct
12	Correct	112 ms	28268 KB	Output is correct
13	Correct	97 ms	28340 KB	Output is correct
14	Correct	104 ms	28248 KB	Output is correct
15	Correct	32 ms	6724 KB	Output is correct
16	Correct	94 ms	27844 KB	Output is correct
17	Correct	124 ms	21572 KB	Output is correct